问一道面世题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

问一道面世题

问一道面世题# JobHunting - 待字闺中

t*r2011-04-22 07:04

1 楼

I have a array which has numbers from 1 to n one number is missing and one
number is duplicated. find those in O(n)
看了career cup
Let arr be the array, d be the duplicate, and m the missing, then we have
(A) N*(N+1)/2 - sum(arr[i]) = d – m
(B) N*(N+1)*(2N+1)/6 - sum(arr[i])^2 = d^2 - m^2
没看懂为啥有B
any thoughs?

m*i2011-04-22 07:04

2 楼

Combine equation A & B, you can solve for d and m.

【在 t******r 的大作中提到】

: I have a array which has numbers from 1 to n one number is missing and one
: number is duplicated. find those in O(n)
: 看了career cup
: Let arr be the array, d be the duplicate, and m the missing, then we have
: (A) N*(N+1)/2 - sum(arr[i]) = d – m
: (B) N*(N+1)*(2N+1)/6 - sum(arr[i])^2 = d^2 - m^2
: 没看懂为啥有B
: any thoughs?

P*a2011-04-22 07:04

3 楼

2个才能解方程啊
B是sigma i^2

【在 t******r 的大作中提到】

m*i2011-04-22 07:04

4 楼

any thought on overflow if N is very large?

【在 P****a 的大作中提到】

: 2个才能解方程啊
: B是sigma i^2

m*l2011-04-22 07:04

5 楼

不能用counting sort吗？

one
have

【在 t******r 的大作中提到】

c*p2011-04-22 07:04

6 楼

位表？不过会要求O(n)的空间。。

【在 t******r 的大作中提到】

m*l2011-04-22 07:04

7 楼

...这是算法耶
brain overflow?

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

: any thought on overflow if N is very large?

m*i2011-04-22 07:04

8 楼

算法就不考虑overflow了？

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

:
: ...这是算法耶
: brain overflow?

m*l2011-04-22 07:04

9 楼

要吗？

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

: 算法就不考虑overflow了？

f*g2011-04-22 07:04

10 楼

XOR 解决

t*r2011-04-22 07:04

11 楼

we'd better to do the left sides of A and B through a loop, instead of using
the formula directly, to avoid overflow. The loop for A's left side is
int aLeft = 0;
for (int i = 0; i < arr.length; ++i) {aLeft += i + 1 - arr[i];}
我的理解就是每次循环求一个差直(比较小),这样就不会溢出了

【在 t******r 的大作中提到】

P*a2011-04-22 07:04

12 楼

恩，这个显然是正解！

using

【在 t******r 的大作中提到】

: we'd better to do the left sides of A and B through a loop, instead of using
: the formula directly, to avoid overflow. The loop for A's left side is
: int aLeft = 0;
: for (int i = 0; i < arr.length; ++i) {aLeft += i + 1 - arr[i];}
: 我的理解就是每次循环求一个差直(比较小),这样就不会溢出了

m*i2011-04-22 07:04

13 楼

nod

【在 P****a 的大作中提到】

: 恩，这个显然是正解！
:
: using

g*e2011-04-22 07:04

14 楼

use xor. O(n) time, O(1) space

【在 t******r 的大作中提到】

m*q2011-04-22 07:04

15 楼

Or use partition, also O(n).
xor is easier in this case.

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

: use xor. O(n) time, O(1) space

g*y2011-04-22 07:04

16 楼

怎么用XOR? 缺一个数，或多一个数，可以理解。但是同时缺，而且多，XOR怎么做？
Like this? or have better algorithm?
====================================================================
Let the missing number is M and the duplicate number is D.
1. Compute X = 1 XOR 2 XOR ... XOR N xor A[1] xor A[2] xor ... xor A[N]
X will be equal to M XOR D. Now find any non-zero bit B of X. It exists because X is not zero.
2. Compute two values
Y = XOR of numbers from 1 to N and elements of array A which have bit B equal 1
Z = XOR of numbers from 1 to N and elements of array A which have bit B equal 0
One of these two numbers will be M and the other will be D.
3. Find which one Y or Z exists in A and therefore is equal to D using one more pass through the array.

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

: use xor. O(n) time, O(1) space

g*y2011-04-22 07:04

17 楼

看到一个很neat的解法：
for (i=1; i<=n; i++) {
swap(a[i], a[a[i]];
}
for (i=1; i<=n; i++) {
if (i != a[i]) {
miss = i;
duplicate = a[i];
}
}

g*e2011-04-22 07:04

18 楼

对，就是这个

because X is not zero.
equal 1
equal 0

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

: 怎么用XOR? 缺一个数，或多一个数，可以理解。但是同时缺，而且多，XOR怎么做？
: Like this? or have better algorithm?
: ====================================================================
: Let the missing number is M and the duplicate number is D.
: 1. Compute X = 1 XOR 2 XOR ... XOR N xor A[1] xor A[2] xor ... xor A[N]
: X will be equal to M XOR D. Now find any non-zero bit B of X. It exists because X is not zero.
: 2. Compute two values
: Y = XOR of numbers from 1 to N and elements of array A which have bit B equal 1
: Z = XOR of numbers from 1 to N and elements of array A which have bit B equal 0
: One of these two numbers will be M and the other will be D.

g*e2011-04-22 07:04

19 楼

这也是经典解法

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

: 看到一个很neat的解法：
: for (i=1; i<=n; i++) {
: swap(a[i], a[a[i]];
: }
: for (i=1; i<=n; i++) {
: if (i != a[i]) {
: miss = i;
: duplicate = a[i];
: }
: }

b*y2011-04-22 07:04

20 楼

bit B是什么

because X is not zero.
equal 1
equal 0

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

g*y2011-04-22 07:04

21 楼

interview时写white board, 绝对愿意写这个，简洁，都没有犯错误的空间。

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

: 这也是经典解法

g*y2011-04-22 07:04

22 楼

any non-zero bit of X

【在 b*******y 的大作中提到】

: bit B是什么
:
: because X is not zero.
: equal 1
: equal 0

g*e2011-04-22 07:04

23 楼

usually we use the right most set bit. you can get this by x & -x

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

: any non-zero bit of X

g*e2011-04-22 07:04

24 楼

这种解法破坏了原来的元素的顺序，面试的人不一定同意

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

: interview时写white board, 绝对愿意写这个，简洁，都没有犯错误的空间。

b*y2011-04-22 07:04

25 楼

没搞明白第一个for循环是干嘛用的

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

: 看到一个很neat的解法：
: for (i=1; i<=n; i++) {
: swap(a[i], a[a[i]];
: }
: for (i=1; i<=n; i++) {
: if (i != a[i]) {
: miss = i;
: duplicate = a[i];
: }
: }

g*y2011-04-22 07:04

26 楼

把数字a[i]送到它该去的位置。循环一遍，所有数归位，只有一个错的，那就是多出来
的那个数，在缺省数的位置。

【在 b*******y 的大作中提到】

: 没搞明白第一个for循环是干嘛用的

b*y2011-04-22 07:04

27 楼

现在明白了谢谢
那么
第一种算法里面
Y和Z找到M和D 的思想是什么

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

: 把数字a[i]送到它该去的位置。循环一遍，所有数归位，只有一个错的，那就是多出来
: 的那个数，在缺省数的位置。

g*y2011-04-22 07:04

28 楼

Bit B 把数组分两组，M，D应该分属两边。然后就归化成用XOR找一个miss/duplicate
数。

【在 b*******y 的大作中提到】

: 现在明白了谢谢
: 那么
: 第一种算法里面
: Y和Z找到M和D 的思想是什么

g*s2011-04-22 07:04

29 楼

这个程序是错的。
换回来的数字还需要继续换，直到换到就是自己。
反例
3 4 2 1

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

: 看到一个很neat的解法：
: for (i=1; i<=n; i++) {
: swap(a[i], a[a[i]];
: }
: for (i=1; i<=n; i++) {
: if (i != a[i]) {
: miss = i;
: duplicate = a[i];
: }
: }

g*e2011-04-22 07:04

30 楼

赞眼尖换了之后要把i-1，其实这里应该用while loop

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

: 这个程序是错的。
: 换回来的数字还需要继续换，直到换到就是自己。
: 反例
: 3 4 2 1

b*y2011-04-22 07:04

31 楼

那也应该是1～N B bit 为1的和数组里面B bit 为1的异或啊

duplicate

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

: Bit B 把数组分两组，M，D应该分属两边。然后就归化成用XOR找一个miss/duplicate
: 数。

g*y2011-04-22 07:04

32 楼

赞！我看到的时候，直觉是把位置i给填上了正确数，没多想。

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

: 这个程序是错的。
: 换回来的数字还需要继续换，直到换到就是自己。
: 反例
: 3 4 2 1

b*y2011-04-22 07:04

33 楼

它程序里面是从Array[1]～Array[N]
不是从Array[0]开始

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

: 赞！我看到的时候，直觉是把位置i给填上了正确数，没多想。

g*y2011-04-22 07:04

34 楼

这个应该可以 work
for (int i=0; iwhile (a[i] != i) {
if (a[i] == a[a[i]]) {
miss = i;
duplicate = a[i];
exit;
}
else {
swap(a[i], a[a[i]]);
}
}
}

g*s2011-04-22 07:04

35 楼

解决了一个问题但来了新的
反例：1 1 2

这个应该可以 workfor (int i=0; i(a[i]="" !="i)" {="........
★ Sent from iPhone App: iReader Mitbbs 6.88 - iPhone Lite

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

: 这个应该可以 work
: for (int i=0; i: while (a[i] != i) {
: if (a[i] == a[a[i]]) {
: miss = i;
: duplicate = a[i];
: exit;
: }
: else {
: swap(a[i], a[a[i]]);

g*e2011-04-22 07:04

36 楼

while会死循环

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

: 这个应该可以 work
: for (int i=0; i: while (a[i] != i) {
: if (a[i] == a[a[i]]) {
: miss = i;
: duplicate = a[i];
: exit;
: }
: else {
: swap(a[i], a[a[i]]);

g*y2011-04-22 07:04

37 楼

good catch! 我写白板肯定fail了。
for (int i=1; i<=n; i++) {
while (a[i] != i) {
if (a[i] == a[a[i]]) {
break;
}
else {
swap(a[i], a[a[i]]);
}
}
}
for (i=1; i<=n; i++) {
if (a[i] != i) {
miss = i;
duplicate = a[i]
}
}

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

: 解决了一个问题但来了新的
: 反例：1 1 2
:
: 这个应该可以 workfor (int i=0; i: (a[i]="" !="i)" {="........
: ★ Sent from iPhone App: iReader Mitbbs 6.88 - iPhone Lite

g*e2011-04-22 07:04

38 楼

for (int i=0; iif (a[i] != a[a[i]-1]) {
swap(a[i], a[a[i]-1]);
i--;
}
}

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

: good catch! 我写白板肯定fail了。
: for (int i=1; i<=n; i++) {
: while (a[i] != i) {
: if (a[i] == a[a[i]]) {
: break;
: }
: else {
: swap(a[i], a[a[i]]);
: }
: }

l*o2011-04-22 07:04

39 楼

我试了一下1 1 2，没发现问题啊？请教一下1，1，2在这个code下有什么问题？

while=""

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

: 解决了一个问题但来了新的
: 反例：1 1 2
:
: 这个应该可以 workfor (int i=0; i: (a[i]="" !="i)" {="........
: ★ Sent from iPhone App: iReader Mitbbs 6.88 - iPhone Lite

m*k2011-04-22 07:04

40 楼

seems this is not always correct. let's simplify it to be an array with 0 to
n-1;
try following in java:
findMissDupFrom0ToNArray(new int[]{6, 0, 1, 2, 6, 5, 4});
out put is
missing 4
duplicated 6, while the real missing one is 3.

h*32011-04-22 07:04

41 楼

这个好像不行把
一个例子：
完整的数组是： 1，2，3，4，5，6
给出的数组A是： 2，3，3，4，5，6 也就是 1 missed, 3 duplicated
x = 1 ^ 3 = 0x10, 非零位为第2位
A 中第2位为1的只有： 2，3，3，6
Y = 1 ^ 3 ^ 4 ^ 5
不是missed 或者duplicated 数。

because X is not zero.
equal 1
equal 0

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

m*P2011-04-22 07:04

42 楼

原帖有点歧义
计算Y和Z时
1到N中的数也只取某BIT为0或1的那些数

【在 h*********3 的大作中提到】

: 这个好像不行把
: 一个例子：
: 完整的数组是： 1，2，3，4，5，6
: 给出的数组A是： 2，3，3，4，5，6 也就是 1 missed, 3 duplicated
: x = 1 ^ 3 = 0x10, 非零位为第2位
: A 中第2位为1的只有： 2，3，3，6
: Y = 1 ^ 3 ^ 4 ^ 5
: 不是missed 或者duplicated 数。
:
: because X is not zero.

c*t2011-04-22 07:04

43 楼

gate 说的是对的。
我写了个完整的：
void get_missing_via_swap(int a[], int n)
{
int i;
for (i = 0; i < n ; i++)
{
if(a[i] != a[a[i]-1])
{
swap(&a[i], &a[a[i]-1]);
i--;
}
}
for(i = 0; i < n; i++)
{
if(a[i] != i+1)
{
printf("the missing number is %d\n", i+1);
printf("the duplicated number is %d\n", a[i]);
break;
}
}
}

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

: for (int i=0; i: if (a[i] != a[a[i]-1]) {
: swap(a[i], a[a[i]-1]);
: i--;
: }
: }