iphone 5 两年合同到期,两条线,每月分钟和数据用的很少,还想用这个手机,有啥好prepaid plan?谢谢。# Apple - 家有苹果t*j2014-08-17 07:081 楼一个integer的数组,其中有一个值出现了两次,还有一个值出现了三次,其他的值都只出现一次。如何找出这两个数。要求空间时间都尽量最优。
r*e2014-08-17 07:083 楼不许用hash table?【在 t*****j 的大作中提到】: 一个integer的数组,其中有一个值出现了两次,还有一个值出现了三次,其他的值都: 只出现一次。如何找出这两个数。要求空间时间都尽量最优。
s*e2014-08-17 07:085 楼又说连续数组吗,然后其他都是一次吗?比如是 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一定可以找出来。
P*02014-08-17 07:086 楼Tmobile★ 发自iPhone App: ChineseWeb 8.2.2【在 h*****6 的大作中提到】: iphone 5 两年合同到期,两条线,每月分钟和数据用的很少,还想用这个手机,有啥: 好prepaid: plan?谢谢。
h*62014-08-17 07:0810 楼半年前回国一次,unlock, 在国内用了一段,现在在美国还能用啊!【在 b***l 的大作中提到】: sprint没戏,要求unlock后都不能在美国用: 除非jb,刷机上pageplus
f*g2014-08-17 07:0813 楼如果是连续的,交换算法最快了吧。不过没说是连续的。我也觉得是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一定可以找出来。
s*52014-08-17 07:0814 楼sorted or not sorted?【在 t*****j 的大作中提到】: 一个integer的数组,其中有一个值出现了两次,还有一个值出现了三次,其他的值都: 只出现一次。如何找出这两个数。要求空间时间都尽量最优。
L*e2014-08-17 07:0815 楼可不可以用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 tripif ( small.size() != 2 ) //errorreturn;map::iterator it = small.begin();if( (*it).second == 2 ) {dup = (*it).first;trip = (*++it).first;}else {trip = (*it).first;dup = (*++it).first;}}
d*o2014-08-17 07:0818 楼我觉得可以 建立一个tree,然后和两个单独的e1,e2.一个个往tree里插, 如果碰到已经存在的, 删除这个点,并放在e1里,以后的每个往里插得都先河e1对比,如果==,就是那个triple,如果不等插到tree里,和前面一样的处理方法。最后肯定会找到,这样空间就是n+2。时间就是 nlogn, 大家觉得如何。
g*y2014-08-17 07:0819 楼这个最坏情况是n^2。如果没有什么更多的条件限制,好象就是把数组排序O(nlogn), 然后扫描O(n)。要想有什么更快的,我觉得肯定得加条件,象数值在一定区域,数字连续,等等。【在 d**********o 的大作中提到】: 我觉得可以 建立一个tree,然后和两个单独的e1,e2.: 一个个往tree里插, 如果碰到已经存在的, 删除这个点,并放在e1里,: 以后的每个往里插得都先河e1对比,如果==,就是那个triple,如果不等插到tree里,: 和前面一样的处理方法。最后肯定会找到,这样空间就是n+2。时间就是 nlogn, 大家觉: 得如何。
y*a2014-08-17 07:0820 楼能详细说说怎么用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一定可以找出来。
g*y2014-08-17 07:0821 楼你写个程序运行一下,除非min=1, max=2^n, XOR(min..max)没什么意义XOR(1..25) = 24XOR(2..25) = 25XOR(3..25) = 27XOR(4..25) = 24XOR(5..25) = 28XOR(6..25) = 25XOR(7..25) = 31XOR(8..25) = 24XOR(9..25) = 16XOR(10..25) = 25XOR(11..25) = 19XOR(12..25) = 24XOR(13..25) = 20XOR(14..25) = 25XOR(15..25) = 23XOR(16..25) = 24XOR(17..25) = 8XOR(18..25) = 25XOR(19..25) = 11XOR(20..25) = 24XOR(21..25) = 12XOR(22..25) = 25XOR(23..25) = 15XOR(24..25) = 24XOR(1..1) = 1XOR(1..2) = 3XOR(1..3) = 0XOR(1..4) = 4XOR(1..5) = 1XOR(1..6) = 7XOR(1..7) = 0XOR(1..8) = 8XOR(1..9) = 1XOR(1..10) = 11XOR(1..11) = 0XOR(1..12) = 12XOR(1..13) = 1XOR(1..14) = 15XOR(1..15) = 0XOR(1..16) = 16XOR(1..17) = 1XOR(1..18) = 19XOR(1..19) = 0XOR(1..20) = 20XOR(1..21) = 1XOR(1..22) = 23XOR(1..23) = 0XOR(1..24) = 24XOR(1..25) = 1在以上的基础上,再XOR一个范围以内的随机数,我看不出有什么规律。【在 y*****a 的大作中提到】: 能详细说说怎么用xor得到出现2次的数吗?每次这种问题大家说用xor的时候都没明白: 怎么弄: : 量extra space一定可以找出来。
y*a2014-08-17 07:0822 楼哦, 我想明白一点了a = [a_1, a_2, a_3, ..., a_n]这个array里的数都是连续的而且在范围[min, max], 如果其中只有a_i 出现了2次,别的都是一次或者三次的话,那么令a_1 ^ a_2 ^ ... ^ a_n = pmin ^ 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
g*y2014-08-17 07:0823 楼要是连续的话,是可以这样,一遍扫描,可以知道:min, max, XOR(array), sum(array)假设a出现2次,b出现3次XOR(array) ^ XOR(min..max) = asum(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