Redian新闻
>
这些找missing number的题是不是都不能用求和做?
avatar
这些找missing number的题是不是都不能用求和做?# JobHunting - 待字闺中
Z*Z
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,是不?
avatar
m*g
2
可以用二分法一网打尽
avatar
k*e
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.
avatar
Z*Z
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.

avatar
Z*Z
5
嗯,对于2个missing2个duplicate的情况,当你2分的时候,怎么知道是求1个呢还是求
2个呢?

【在 m*****g 的大作中提到】
: 可以用二分法一网打尽
avatar
b*r
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
avatar
w*1
7
why not use the hash table?
avatar
y*n
8
agree, a bit map is sufficient since we know the range of the elements.

【在 w******1 的大作中提到】
: why not use the hash table?
avatar
f*5
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,是不?

avatar
Z*Z
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]: }

avatar
a*d
11
If #1 problem is changed to array of N-1 element, then we can use bit XOR
operation to find the missing number.
avatar
l*q
12
如果只有2个,还是可以求的
这种情况下,xor的结果一定不为0 ==〉至少有一位是1
把这位是1和0的分为两组,这又变成只有1个dupliate了,再分别求一次xor

【在 Z*****Z 的大作中提到】
: 嗯,对于2个missing2个duplicate的情况,当你2分的时候,怎么知道是求1个呢还是求
: 2个呢?

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

【在 l****q 的大作中提到】
: 如果只有2个,还是可以求的
: 这种情况下,xor的结果一定不为0 ==〉至少有一位是1
: 把这位是1和0的分为两组,这又变成只有1个dupliate了,再分别求一次xor

avatar
r*o
14
第一组的数这个比特都是1,第二组的数这个比特都是0啊。

【在 Z*****Z 的大作中提到】
: 不太明白,duplicate的元素做XOR肯定是0。所以,对原数组所有元素做XOR相当于对原
: 数组所有unique元素做XOR。
: 为什么结果一定不为0,为什么根据为1的某位,能把duplicate分到2组去?

avatar
Z*Z
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

avatar
a*d
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]: }

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