Z*****Z
发帖数: 723 | 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*****g
发帖数: 226 | |
k****e
发帖数: 337 | 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*****Z
发帖数: 723 | 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*****Z
发帖数: 723 | 5 嗯，对于2个missing2个duplicate的情况，当你2分的时候，怎么知道是求1个呢还是求
2个呢？
【在 m*****g 的大作中提到】
: 可以用二分法一网打尽
|
b****r
发帖数: 1272 | 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******1
发帖数: 520 | 7 why not use the hash table? |
y****n
发帖数: 579 | 8 agree, a bit map is sufficient since we know the range of the elements.
【在 w******1 的大作中提到】
: why not use the hash table?
|
f*********5
发帖数: 576 | 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*****Z
发帖数: 723 | 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*d
发帖数: 47 | 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****q
发帖数: 177 | 12 如果只有2个，还是可以求的
这种情况下，xor的结果一定不为0 ==〉至少有一位是1
把这位是1和0的分为两组，这又变成只有1个dupliate了，再分别求一次xor
【在 Z*****Z 的大作中提到】
: 嗯，对于2个missing2个duplicate的情况，当你2分的时候，怎么知道是求1个呢还是求
: 2个呢？
|
Z*****Z
发帖数: 723 | 13 不太明白，duplicate的元素做XOR肯定是0。所以，对原数组所有元素做XOR相当于对原
数组所有unique元素做XOR。
为什么结果一定不为0，为什么根据为1的某位，能把duplicate分到2组去？
【在 l****q 的大作中提到】
: 如果只有2个，还是可以求的
: 这种情况下，xor的结果一定不为0 ==〉至少有一位是1
: 把这位是1和0的分为两组，这又变成只有1个dupliate了，再分别求一次xor
|
r****o
发帖数: 1950 | 14 第一组的数这个比特都是1，第二组的数这个比特都是0啊。
【在 Z*****Z 的大作中提到】
: 不太明白，duplicate的元素做XOR肯定是0。所以，对原数组所有元素做XOR相当于对原
: 数组所有unique元素做XOR。
: 为什么结果一定不为0，为什么根据为1的某位，能把duplicate分到2组去？
|
Z*****Z
发帖数: 723 | 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 的大作中提到】
: 如果只有2个，还是可以求的
: 这种情况下，xor的结果一定不为0 ==〉至少有一位是1
: 把这位是1和0的分为两组，这又变成只有1个dupliate了，再分别求一次xor
|
a*d
发帖数: 47 | 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]: }
|
