这些找missing number的题是不是都不能用求和做？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

这些找missing number的题是不是都不能用求和做？

这些找missing number的题是不是都不能用求和做？# JobHunting - 待字闺中

Z*Z2010-05-24 07:05

1 楼

# Given an array of size n. It contains numbers in the range 1 to n. Each
number is present at least once except for 1 number. Find the missing number.
# Given an array of size n. It contains numbers in the range 1 to n. Each nu
mber is present at least once except for 2 numbers. Find the missing numbers
.
# Given an array of size n. It contains numbers in the range 1 to n. Find th
e numbers which aren’t present.
优化空间的话就sort;否则就开一个size 为N的array，是不？

m*g2010-05-24 07:05

2 楼

可以用二分法一网打尽

k*e2010-05-24 07:05

3 楼

first:　one is missing and one is duplicate
two equations: sum = 1+ 2 + 3 + ... + N + x - y
square. s = 1^2 + 2^2 + .... + N^2 + X^2 - Y^2
sorting. you know the max, so you can use a sorting method, o(n).
I have the source code.

Z*Z2010-05-24 07:05

4 楼

哦，这样，那么有2个missing2个duplicate的话列到4次方理论上也成吧？

【在 k****e 的大作中提到】

: first:　one is missing and one is duplicate
: two equations: sum = 1+ 2 + 3 + ... + N + x - y
: square. s = 1^2 + 2^2 + .... + N^2 + X^2 - Y^2
: sorting. you know the max, so you can use a sorting method, o(n).
: I have the source code.

Z*Z2010-05-24 07:05

5 楼

嗯，对于2个missing2个duplicate的情况，当你2分的时候，怎么知道是求1个呢还是求
2个呢？

【在 m*****g 的大作中提到】

: 可以用二分法一网打尽

b*r2010-05-24 07:05

6 楼

sum method will suffer overflow issues and may no tbe what interviewers are
looking for
for 1 missing number, one can use bitwise (2^n-1) searching - count # of 0s
and 1s at each digit
for >1 missing numbers, binary search is one of the approaches

w*12010-05-24 07:05

7 楼

why not use the hash table?

y*n2010-05-24 07:05

8 楼

agree, a bit map is sufficient since we know the range of the elements.

【在 w******1 的大作中提到】

: why not use the hash table?

f*52010-05-24 07:05

9 楼

if distroying the array is supoorted,you can use below logic to get all
the answers
for (i=0;i{
a[a[i]%(n+1)-1]+=n+1;
}
for(i=0;i{
if(a[i]}

Each
number.
Each nu
numbers
Find th

【在 Z*****Z 的大作中提到】

: # Given an array of size n. It contains numbers in the range 1 to n. Each
: number is present at least once except for 1 number. Find the missing number.
: # Given an array of size n. It contains numbers in the range 1 to n. Each nu
: mber is present at least once except for 2 numbers. Find the missing numbers
: .
: # Given an array of size n. It contains numbers in the range 1 to n. Find th
: e numbers which aren’t present.
: 优化空间的话就sort;否则就开一个size 为N的array，是不？

Z*Z2010-05-24 07:05

10 楼

哈哈，学习了！~

【在 f*********5 的大作中提到】

: if distroying the array is supoorted,you can use below logic to get all
: the answers
: for (i=0;i: {
: a[a[i]%(n+1)-1]+=n+1;
: }
: for(i=0;i: {
: if(a[i]: }

a*d2010-05-24 07:05

11 楼

If #1 problem is changed to array of N-1 element, then we can use bit XOR
operation to find the missing number.

l*q2010-05-24 07:05

12 楼

如果只有2个，还是可以求的
这种情况下，xor的结果一定不为0 ==〉至少有一位是1
把这位是1和0的分为两组，这又变成只有1个dupliate了，再分别求一次xor

【在 Z*****Z 的大作中提到】

: 嗯，对于2个missing2个duplicate的情况，当你2分的时候，怎么知道是求1个呢还是求
: 2个呢？

Z*Z2010-05-24 07:05

13 楼

不太明白，duplicate的元素做XOR肯定是0。所以，对原数组所有元素做XOR相当于对原
数组所有unique元素做XOR。
为什么结果一定不为0，为什么根据为1的某位，能把duplicate分到2组去？

【在 l****q 的大作中提到】

: 如果只有2个，还是可以求的
: 这种情况下，xor的结果一定不为0 ==〉至少有一位是1
: 把这位是1和0的分为两组，这又变成只有1个dupliate了，再分别求一次xor

r*o2010-05-24 07:05

14 楼

第一组的数这个比特都是1，第二组的数这个比特都是0啊。

【在 Z*****Z 的大作中提到】

: 不太明白，duplicate的元素做XOR肯定是0。所以，对原数组所有元素做XOR相当于对原
: 数组所有unique元素做XOR。
: 为什么结果一定不为0，为什么根据为1的某位，能把duplicate分到2组去？

Z*Z2010-05-24 07:05

15 楼

举例：1到7的数组，现在5和6missing，1和2duplicate，也就是说：
1,1,2,2,3,4,7
做XOR的结果相当于3，4,7做抑或，结果为0。
这个方法甚至于对1个missing1个duplicate的也不work，举例：
1到6的数组，6 missing 1 duplicate，也就是说
1,1,2,3,4,5
做抑或的结果还是0
除非我对你这里做抑或的理解有误

【在 l****q 的大作中提到】

a*d2010-05-24 07:05

16 楼

This effectively merges the additional array into existing array, provided
that you can differentiate them by the non-overlapping value range.
This is not working if N > value_range/2.

【在 f*********5 的大作中提到】

: if distroying the array is supoorted,you can use below logic to get all
: the answers
: for (i=0;i: {
: a[a[i]%(n+1)-1]+=n+1;
: }
: for(i=0;i: {
: if(a[i]: }