Redian新闻
>
iphone 5 两年合同到期,两条线,每月分钟和数据用的很少,还想用这个手机,有啥好prepaid plan?谢谢。
avatar
iphone 5 两年合同到期,两条线,每月分钟和数据用的很少,还想用这个手机,有啥好prepaid plan?谢谢。# Apple - 家有苹果
t*j
1
一个integer的数组,其中有一个值出现了两次,还有一个值出现了三次,其他的值都
只出现一次。如何找出这两个数。要求空间时间都尽量最优。
avatar
h*6
2
iphone 5 两年合同到期,两条线,每月分钟和数据用的很少,还想用这个手机,有啥
好prepaid
plan?谢谢。
avatar
r*e
3
不许用hash table?

【在 t*****j 的大作中提到】
: 一个integer的数组,其中有一个值出现了两次,还有一个值出现了三次,其他的值都
: 只出现一次。如何找出这两个数。要求空间时间都尽量最优。

avatar
h*6
4
原来是sprint的两年服务。
谁能推荐个好的prepaid plan?
谢谢。
avatar
s*e
5
又说连续数组吗,然后其他都是一次吗?
比如是 1 2 2 2 3 4 5 5 6 这样,
还是完全random的,比如: 1 2 2 2 7 7 8 10
?
如果是后者,估计就是先看能不能用hash,如果不能用外部空间就先排序再一个一个扫
如果是前者,我猜是先 xor 所有数 以及 min 到 max的所有数,
然后得到出现2次的那个。
然后要找出现3次那个,把所有数加起来?这样问题是可能overflow,但是O(n)没有大量extra space一定可以找出来。
avatar
P*0
6
Tmobile

★ 发自iPhone App: ChineseWeb 8.2.2

【在 h*****6 的大作中提到】
: iphone 5 两年合同到期,两条线,每月分钟和数据用的很少,还想用这个手机,有啥
: 好prepaid
: plan?谢谢。

avatar
s*e
7
btw 楼主签名档2年2月2周2天 赞
avatar
b*l
8
sprint没戏,要求unlock后都不能在美国用
除非jb,刷机上pageplus
avatar
t*j
9
要求时间空间尽量最优,hash table空间花费比较大。

【在 r*******e 的大作中提到】
: 不许用hash table?
avatar
h*6
10
半年前回国一次,unlock, 在国内用了一段,现在在美国还能用啊!

【在 b***l 的大作中提到】
: sprint没戏,要求unlock后都不能在美国用
: 除非jb,刷机上pageplus

avatar
t*j
11
谢啊,你不说我还没注意...

【在 s*******e 的大作中提到】
: btw 楼主签名档2年2月2周2天 赞
avatar
f*g
12
If the data is distributed in a small range, then use bitmap.
avatar
f*g
13
如果是连续的,交换算法最快了吧。
不过没说是连续的。
我也觉得是bitset, 需要两个。

量extra space一定可以找出来。

【在 s*******e 的大作中提到】
: 又说连续数组吗,然后其他都是一次吗?
: 比如是 1 2 2 2 3 4 5 5 6 这样,
: 还是完全random的,比如: 1 2 2 2 7 7 8 10
: ?
: 如果是后者,估计就是先看能不能用hash,如果不能用外部空间就先排序再一个一个扫
: 如果是前者,我猜是先 xor 所有数 以及 min 到 max的所有数,
: 然后得到出现2次的那个。
: 然后要找出现3次那个,把所有数加起来?这样问题是可能overflow,但是O(n)没有大量extra space一定可以找出来。

avatar
s*5
14

sorted or not sorted?

【在 t*****j 的大作中提到】
: 一个integer的数组,其中有一个值出现了两次,还有一个值出现了三次,其他的值都
: 只出现一次。如何找出这两个数。要求空间时间都尽量最优。

avatar
L*e
15
可不可以用vector + small map variables, like the following:
/* assume range 'from' ... 'to' */
void findDupTri(int a[], size_t size, int from, int to, int& dup, int& trip)
{
vector v( to-from+1, false);
map small;
for( int i = 0; i < size; i++ ){
if( v[a[i]-from] == true ) {
small[a[i]]++;
}
else{
v[a[i]-from] = true;
}
}
// scan the map to find dup and trip
if ( small.size() != 2 ) //error
return;
map::iterator it = small.begin();
if( (*it).second == 2 ) {
dup = (*it).first;
trip = (*++it).first;
}
else {
trip = (*it).first;
dup = (*++it).first;
}
}
avatar
l*i
16
想到了bitmap
但是如果数组的范围很大或者未知,bitmap也不合适
这个题目对数组里面的数有限制吗?
avatar
l*v
17
如果range大可以先sort再loop O(lgn*n)
avatar
d*o
18
我觉得可以 建立一个tree,然后和两个单独的e1,e2.
一个个往tree里插, 如果碰到已经存在的, 删除这个点,并放在e1里,
以后的每个往里插得都先河e1对比,如果==,就是那个triple,如果不等插到tree里,
和前面一样的处理方法。最后肯定会找到,这样空间就是n+2。时间就是 nlogn, 大家觉
得如何。
avatar
g*y
19
这个最坏情况是n^2。
如果没有什么更多的条件限制,好象就是把数组排序O(nlogn), 然后扫描O(n)。
要想有什么更快的,我觉得肯定得加条件,象数值在一定区域,数字连续,等等。

【在 d**********o 的大作中提到】
: 我觉得可以 建立一个tree,然后和两个单独的e1,e2.
: 一个个往tree里插, 如果碰到已经存在的, 删除这个点,并放在e1里,
: 以后的每个往里插得都先河e1对比,如果==,就是那个triple,如果不等插到tree里,
: 和前面一样的处理方法。最后肯定会找到,这样空间就是n+2。时间就是 nlogn, 大家觉
: 得如何。

avatar
y*a
20
能详细说说怎么用xor得到出现2次的数吗?每次这种问题大家说用xor的时候都没明白
怎么弄

量extra space一定可以找出来。

【在 s*******e 的大作中提到】
: 又说连续数组吗,然后其他都是一次吗?
: 比如是 1 2 2 2 3 4 5 5 6 这样,
: 还是完全random的,比如: 1 2 2 2 7 7 8 10
: ?
: 如果是后者,估计就是先看能不能用hash,如果不能用外部空间就先排序再一个一个扫
: 如果是前者,我猜是先 xor 所有数 以及 min 到 max的所有数,
: 然后得到出现2次的那个。
: 然后要找出现3次那个,把所有数加起来?这样问题是可能overflow,但是O(n)没有大量extra space一定可以找出来。

avatar
g*y
21
你写个程序运行一下,除非min=1, max=2^n, XOR(min..max)没什么意义
XOR(1..25) = 24
XOR(2..25) = 25
XOR(3..25) = 27
XOR(4..25) = 24
XOR(5..25) = 28
XOR(6..25) = 25
XOR(7..25) = 31
XOR(8..25) = 24
XOR(9..25) = 16
XOR(10..25) = 25
XOR(11..25) = 19
XOR(12..25) = 24
XOR(13..25) = 20
XOR(14..25) = 25
XOR(15..25) = 23
XOR(16..25) = 24
XOR(17..25) = 8
XOR(18..25) = 25
XOR(19..25) = 11
XOR(20..25) = 24
XOR(21..25) = 12
XOR(22..25) = 25
XOR(23..25) = 15
XOR(24..25) = 24
XOR(1..1) = 1
XOR(1..2) = 3
XOR(1..3) = 0
XOR(1..4) = 4
XOR(1..5) = 1
XOR(1..6) = 7
XOR(1..7) = 0
XOR(1..8) = 8
XOR(1..9) = 1
XOR(1..10) = 11
XOR(1..11) = 0
XOR(1..12) = 12
XOR(1..13) = 1
XOR(1..14) = 15
XOR(1..15) = 0
XOR(1..16) = 16
XOR(1..17) = 1
XOR(1..18) = 19
XOR(1..19) = 0
XOR(1..20) = 20
XOR(1..21) = 1
XOR(1..22) = 23
XOR(1..23) = 0
XOR(1..24) = 24
XOR(1..25) = 1
在以上的基础上,再XOR一个范围以内的随机数,我看不出有什么规律。

【在 y*****a 的大作中提到】
: 能详细说说怎么用xor得到出现2次的数吗?每次这种问题大家说用xor的时候都没明白
: 怎么弄
:
: 量extra space一定可以找出来。

avatar
y*a
22
哦, 我想明白一点了
a = [a_1, a_2, a_3, ..., a_n]
这个array里的数都是连续的而且在范围[min, max], 如果其中只有a_i 出现了2次,别的都是一次或者三次的话,那么令
a_1 ^ a_2 ^ ... ^ a_n = p
min ^ min+1 ^ ... ^ max = q
就有p = q ^ a_i 也就是说 a_i = p ^ q
这样知道p, q就可以算出a_i

【在 g**********y 的大作中提到】
: 你写个程序运行一下,除非min=1, max=2^n, XOR(min..max)没什么意义
: XOR(1..25) = 24
: XOR(2..25) = 25
: XOR(3..25) = 27
: XOR(4..25) = 24
: XOR(5..25) = 28
: XOR(6..25) = 25
: XOR(7..25) = 31
: XOR(8..25) = 24
: XOR(9..25) = 16

avatar
g*y
23
要是连续的话,是可以这样,
一遍扫描,可以知道:min, max, XOR(array), sum(array)
假设a出现2次,b出现3次
XOR(array) ^ XOR(min..max) = a
sum(array) - sum(min..max) = a + 2b

别的都是一次或者三次的话,那么令

【在 y*****a 的大作中提到】
: 哦, 我想明白一点了
: a = [a_1, a_2, a_3, ..., a_n]
: 这个array里的数都是连续的而且在范围[min, max], 如果其中只有a_i 出现了2次,别的都是一次或者三次的话,那么令
: a_1 ^ a_2 ^ ... ^ a_n = p
: min ^ min+1 ^ ... ^ max = q
: 就有p = q ^ a_i 也就是说 a_i = p ^ q
: 这样知道p, q就可以算出a_i

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。