t*****j
发帖数: 1105 | 1 一个integer的数组，其中有一个值出现了两次，还有一个值出现了三次，其他的值都
只出现一次。如何找出这两个数。要求空间时间都尽量最优。 |
r*******e
发帖数: 7583 | 2 不许用hash table？
【在 t*****j 的大作中提到】
: 一个integer的数组，其中有一个值出现了两次，还有一个值出现了三次，其他的值都
: 只出现一次。如何找出这两个数。要求空间时间都尽量最优。
|
s*******e
发帖数: 93 | 3 又说连续数组吗，然后其他都是一次吗？
比如是 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*******e
发帖数: 93 | |
t*****j
发帖数: 1105 | 5 要求时间空间尽量最优，hash table空间花费比较大。
【在 r*******e 的大作中提到】
: 不许用hash table？
|
t*****j
发帖数: 1105 | 6 谢啊，你不说我还没注意...
【在 s*******e 的大作中提到】
: btw 楼主签名档2年2月2周2天 赞
|
f****g
发帖数: 313 | 7 If the data is distributed in a small range, then use bitmap. |
f***g
发帖数: 214 | 8 如果是连续的，交换算法最快了吧。
不过没说是连续的。
我也觉得是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******5
发帖数: 673 | 9
sorted or not sorted?
【在 t*****j 的大作中提到】
: 一个integer的数组，其中有一个值出现了两次，还有一个值出现了三次，其他的值都
: 只出现一次。如何找出这两个数。要求空间时间都尽量最优。
|
L*******e
发帖数: 114 | 10 可不可以用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;
}
} |
|
|
l****i
发帖数: 396 | 11 想到了bitmap
但是如果数组的范围很大或者未知，bitmap也不合适
这个题目对数组里面的数有限制吗？ |
l*****v
发帖数: 498 | 12 如果range大可以先sort再loop O(lgn*n) |
d**********o
发帖数: 279 | 13 我觉得可以 建立一个tree,然后和两个单独的e1,e2.
一个个往tree里插， 如果碰到已经存在的， 删除这个点，并放在e1里，
以后的每个往里插得都先河e1对比，如果==，就是那个triple,如果不等插到tree里，
和前面一样的处理方法。最后肯定会找到,这样空间就是n+2。时间就是 nlogn, 大家觉
得如何。 |
g**********y
发帖数: 14569 | 14 这个最坏情况是n^2。
如果没有什么更多的条件限制，好象就是把数组排序O(nlogn), 然后扫描O(n)。
要想有什么更快的，我觉得肯定得加条件，象数值在一定区域，数字连续，等等。
【在 d**********o 的大作中提到】
: 我觉得可以 建立一个tree,然后和两个单独的e1,e2.
: 一个个往tree里插， 如果碰到已经存在的， 删除这个点，并放在e1里，
: 以后的每个往里插得都先河e1对比，如果==，就是那个triple,如果不等插到tree里，
: 和前面一样的处理方法。最后肯定会找到,这样空间就是n+2。时间就是 nlogn, 大家觉
: 得如何。
|
y*****a
发帖数: 221 | 15 能详细说说怎么用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**********y
发帖数: 14569 | 16 你写个程序运行一下，除非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一定可以找出来。
|
y*****a
发帖数: 221 | 17 哦， 我想明白一点了
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
|
g**********y
发帖数: 14569 | 18 要是连续的话，是可以这样，
一遍扫描，可以知道：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
|
