t******r
发帖数: 209 | 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***i
发帖数: 398 | 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****a
发帖数: 864 | 3 2个才能解方程啊
B是sigma i^2
【在 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?
|
m***i
发帖数: 398 | 4 any thought on overflow if N is very large?
【在 P****a 的大作中提到】
: 2个才能解方程啊
: B是sigma i^2
|
m********l
发帖数: 4394 | 5 不能用counting sort吗？
one
have
【在 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?
|
c****p
发帖数: 6474 | 6 位表？不过会要求O(n)的空间。。
【在 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?
|
m********l
发帖数: 4394 | 7
...这是算法耶
brain overflow?
【在 m***i 的大作中提到】
: any thought on overflow if N is very large?
|
m***i
发帖数: 398 | 8 算法就不考虑overflow了？
【在 m********l 的大作中提到】
:
: ...这是算法耶
: brain overflow?
|
m********l
发帖数: 4394 | 9
要吗？
【在 m***i 的大作中提到】
: 算法就不考虑overflow了？
|
f***g
发帖数: 214 | |
|
|
t******r
发帖数: 209 | 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 的大作中提到】
: 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****a
发帖数: 864 | 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***i
发帖数: 398 | 13 nod
【在 P****a 的大作中提到】
: 恩，这个显然是正解！
:
: using
|
g**e
发帖数: 6127 | 14 use xor. O(n) time, O(1) space
【在 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?
|
m**q
发帖数: 189 | 15 Or use partition, also O(n).
xor is easier in this case.
【在 g**e 的大作中提到】
: use xor. O(n) time, O(1) space
|
g**********y
发帖数: 14569 | 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**********y
发帖数: 14569 | 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**e
发帖数: 6127 | 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**e
发帖数: 6127 | 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*******y
发帖数: 1240 | 20 bit B是什么
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**********y
发帖数: 14569 | 21 interview时写white board, 绝对愿意写这个，简洁，都没有犯错误的空间。
【在 g**e 的大作中提到】
: 这也是经典解法
|
g**********y
发帖数: 14569 | 22 any non-zero bit of X
【在 b*******y 的大作中提到】
: bit B是什么
:
: because X is not zero.
: equal 1
: equal 0
|
g**e
发帖数: 6127 | 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**e
发帖数: 6127 | 24 这种解法破坏了原来的元素的顺序，面试的人不一定同意
【在 g**********y 的大作中提到】
: interview时写white board, 绝对愿意写这个，简洁，都没有犯错误的空间。
|
b*******y
发帖数: 1240 | 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**********y
发帖数: 14569 | 26 把数字a[i]送到它该去的位置。循环一遍，所有数归位，只有一个错的，那就是多出来
的那个数，在缺省数的位置。
【在 b*******y 的大作中提到】
: 没搞明白第一个for循环是干嘛用的
|
b*******y
发帖数: 1240 | 27 现在明白了谢谢
那么
第一种算法里面
Y和Z找到M和D 的思想是什么
【在 g**********y 的大作中提到】
: 把数字a[i]送到它该去的位置。循环一遍，所有数归位，只有一个错的，那就是多出来
: 的那个数，在缺省数的位置。
|
g**********y
发帖数: 14569 | 28 Bit B 把数组分两组，M，D应该分属两边。然后就归化成用XOR找一个miss/duplicate
数。
【在 b*******y 的大作中提到】
: 现在明白了谢谢
: 那么
: 第一种算法里面
: Y和Z找到M和D 的思想是什么
|
g***s
发帖数: 3811 | 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**e
发帖数: 6127 | 30 赞眼尖 换了之后要把i-1，其实这里应该用while loop
【在 g***s 的大作中提到】
: 这个程序是错的。
: 换回来的数字还需要继续换，直到换到就是自己。
: 反例
: 3 4 2 1
|
|
|
b*******y
发帖数: 1240 | 31 那也应该是1～N B bit 为1的和数组里面B bit 为1的异或啊
duplicate
【在 g**********y 的大作中提到】
: Bit B 把数组分两组，M，D应该分属两边。然后就归化成用XOR找一个miss/duplicate
: 数。
|
g**********y
发帖数: 14569 | 32 赞！我看到的时候，直觉是把位置i给填上了正确数，没多想。
【在 g***s 的大作中提到】
: 这个程序是错的。
: 换回来的数字还需要继续换，直到换到就是自己。
: 反例
: 3 4 2 1
|
b*******y
发帖数: 1240 | 33 它程序里面是从Array[1]～Array[N]
不是从Array[0]开始
【在 g**********y 的大作中提到】
: 赞！我看到的时候，直觉是把位置i给填上了正确数，没多想。
|
g**********y
发帖数: 14569 | 34 这个应该可以 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***s
发帖数: 3811 | 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**e
发帖数: 6127 | 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**********y
发帖数: 14569 | 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**e
发帖数: 6127 | 38 for (int i=0; i
if (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****o
发帖数: 43 | 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*****k
发帖数: 731 | 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*********3
发帖数: 111 | 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 的大作中提到】
: 怎么用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.
|
m*****P
发帖数: 1331 | 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*********t
发帖数: 2921 | 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--;
: }
: }
|
