c*******r
发帖数: 309 | 1 数组只有1-10000，然后size是10001，怎么找到重复的那个
ONSITE题目，让用尽可能多的方法。我能想到的方法是sum之后做减法， Hashtable,
sorting完扫一边， 或者boolean数组存。
当时二逼用了swap的算法不停swap，结果最后自己没弄出来。
想问下这题有什么比较好的解法啊？ |
j*********6
发帖数: 407 | |
s*******r
发帖数: 2697 | 3 O(n)
int findDup(int []a,int n){
long ret=0;
for(int i=0;i
ret+=a[i]-i;
}
return ret;
} |
c*****a
发帖数: 808 | |
f*******t
发帖数: 7549 | 5 最优解：
int findDup(int[] A) {
int ans = 0;
for (int i = 0; i < n; i++) {
ans ^= A[i];
ans ^= i;
}
return ans;
} |
c*******r
发帖数: 309 | 6 O(n). 一个小bug, i<=n
int findDup(int []a,int n){
long ret=0;
for(int i=0;i
ret+=a[i]-i;
}
return ret;
} |
G****A
发帖数: 4160 | 7 这个小trick不错
【在 s*******r 的大作中提到】
: O(n)
: int findDup(int []a,int n){
: long ret=0;
: for(int i=0;i: ret+=a[i]-i;
: }
: return ret;
: }
|
m*****1
发帖数: 147 | 8 你怎么知道挂在这个题上面？？你已经给出不少答案了啊 |
c*******r
发帖数: 309 | 9 我自己一口气说出来以后手贱写了个之前板上看到的swap()的方法，其实复杂度也不咋
地，结果写出问题了... |
g****y
发帖数: 2810 | 10 这个真不错，还省去了算总和的时间
【在 f*******t 的大作中提到】
: 最优解：
: int findDup(int[] A) {
: int ans = 0;
: for (int i = 0; i < n; i++) {
: ans ^= A[i];
: ans ^= i;
: }
: return ans;
: }
|
|
|
d**e
发帖数: 6098 | 11 这个方法妙得很！
【在 s*******r 的大作中提到】
: O(n)
: int findDup(int []a,int n){
: long ret=0;
: for(int i=0;i: ret+=a[i]-i;
: }
: return ret;
: }
|
d**********o
发帖数: 11 | 12 这个也是 O(N)
为啥最优？
是因为bit运算比较快吗？
【在 f*******t 的大作中提到】
: 最优解：
: int findDup(int[] A) {
: int ans = 0;
: for (int i = 0; i < n; i++) {
: ans ^= A[i];
: ans ^= i;
: }
: return ans;
: }
|
d*******3
发帖数: 58 | 13 O(n)是最好的了，这个是O(N）里的最好的了，空间O(1),而且位运算比加减快
【在 d**********o 的大作中提到】
: 这个也是 O(N)
: 为啥最优？
: 是因为bit运算比较快吗？
|
v***n
发帖数: 562 | |
f*******t
发帖数: 7549 | 15 做加法写的不好还有溢出的风险
【在 d**********o 的大作中提到】
: 这个也是 O(N)
: 为啥最优？
: 是因为bit运算比较快吗？
|
r********9
发帖数: 1116 | 16 是这样的swap算法吗？也是O(n).
int f(int *a, int n){
int tmp;
for(int i=0; i
while(a[i]!=i+1){
tmp=a[i];
a[i]=a[a[i]-1];
if(tmp==a[i]) return tmp;
else{
a[a[i]-1]=tmp;
}
}
}
return -1;
}
【在 c*******r 的大作中提到】
: 我自己一口气说出来以后手贱写了个之前板上看到的swap()的方法，其实复杂度也不咋
: 地，结果写出问题了...
|
e***s
发帖数: 799 | 17 拜服。秒杀的解法
【在 f*******t 的大作中提到】
: 最优解：
: int findDup(int[] A) {
: int ans = 0;
: for (int i = 0; i < n; i++) {
: ans ^= A[i];
: ans ^= i;
: }
: return ans;
: }
|
l*********8
发帖数: 4642 | 18 这个还是可能溢出。
【在 c*******r 的大作中提到】
: O(n). 一个小bug, i<=n
: int findDup(int []a,int n){
: long ret=0;
: for(int i=0;i: ret+=a[i]-i;
: }
: return ret;
: }
|
k*******t
发帖数: 144 | 19 有个疑问，如果这个数组是sorted, 是不是可以用binary search？每次看到一个元素
，比较小相邻的两个值，没有相等的话，再根据index和对应的值决定向左或向右。这
样只要O(lgn), 不知这个有没有什么问题？ |
s*******r
发帖数: 2697 | 20 你再仔细想想
【在 c*******r 的大作中提到】
: O(n). 一个小bug, i<=n
: int findDup(int []a,int n){
: long ret=0;
: for(int i=0;i: ret+=a[i]-i;
: }
: return ret;
: }
|
|
|
s*******r
发帖数: 2697 | 21 对lz的题目不会溢出
当数组size大到一定程度而且内存能装的下的话
是可能溢出的
位操作可以保证不会溢出
【在 l*********8 的大作中提到】
: 这个还是可能溢出。
|
s*******r
发帖数: 2697 | 22 没问题
不过不需要比较相邻的两个值 直接比较a[i]和i就可以
【在 k*******t 的大作中提到】
: 有个疑问，如果这个数组是sorted, 是不是可以用binary search？每次看到一个元素
: ，比较小相邻的两个值，没有相等的话，再根据index和对应的值决定向左或向右。这
: 样只要O(lgn), 不知这个有没有什么问题？
|
k*******t
发帖数: 144 | 23
确实，谢谢拉
【在 s*******r 的大作中提到】
: 没问题
: 不过不需要比较相邻的两个值 直接比较a[i]和i就可以
|
t*****h
发帖数: 137 | 24 如果swap的cost和位运算的一样，应该是swap更好。 |
f*******t
发帖数: 7549 | 25 我觉得swap不如位运算。
位运算是把N+1个数全读一遍。
swap概率上平均要读(N+1)/4个数，但对每个数，需要做swap操作的概率是N/(N+1)。也
就是说，要进行N/4次swap。swap的cost不止是位运算的4倍吧。
【在 t*****h 的大作中提到】
: 如果swap的cost和位运算的一样，应该是swap更好。
|
r*****o
发帖数: 5 | 26 这两个O(n)的算法假定数组是sorted的吧？
如果不是sorted有啥好解法？先排序么？ |
s*******s
发帖数: 1031 | 27 我觉得这个swap应该没问题吧，你当初是这么写的？
// O(n)
int findDuplicate(vector A) {
// let A[i] == i for i=1, 2, ..., 1000
while(A[0] != A[A[0]]) {
swap(A[0], A[A[0]];
}
return A[0];
}
【在 c*******r 的大作中提到】
: 我自己一口气说出来以后手贱写了个之前板上看到的swap()的方法，其实复杂度也不咋
: 地，结果写出问题了...
|
l*****s
发帖数: 774 | 28 这个不对，while外面还应该有一层循环
【在 s*******s 的大作中提到】
: 我觉得这个swap应该没问题吧，你当初是这么写的？
: // O(n)
: int findDuplicate(vector A) {
: // let A[i] == i for i=1, 2, ..., 1000
: while(A[0] != A[A[0]]) {
: swap(A[0], A[A[0]];
: }
: return A[0];
: }
|
b***i
发帖数: 3043 | 29
最优解：
int findDup(int[] A, int n) {
int ans = n;
【在 f*******t 的大作中提到】
: 最优解：
: int findDup(int[] A) {
: int ans = 0;
: for (int i = 0; i < n; i++) {
: ans ^= A[i];
: ans ^= i;
: }
: return ans;
: }
|
s*******s
发帖数: 1031 | 30 我觉得不用一个外层循环了，
前提条件是1－10000这10000个数放到10001个slot中，而且只有一个重复。
我们只要能找到一个A[A[0]] == A[0]就足够了。
你觉得呢？
【在 l*****s 的大作中提到】
: 这个不对，while外面还应该有一层循环
|
|
|
s*******s
发帖数: 1031 | 31 这个最初的ans应该初始化成0吧？
【在 b***i 的大作中提到】
:
: 最优解：
: int findDup(int[] A, int n) {
: int ans = n;
|
b***i
发帖数: 3043 | 32 you are right, I was starting from 1
【在 s*******s 的大作中提到】
: 这个最初的ans应该初始化成0吧？
|
b***i
发帖数: 3043 | 33 not really. Please gives code
【在 s*******r 的大作中提到】
: 对lz的题目不会溢出
: 当数组size大到一定程度而且内存能装的下的话
: 是可能溢出的
: 位操作可以保证不会溢出
|
w**********o
发帖数: 140 | 34
這個能找到duplicates regardless of the range, as long as there's only one
duplicate.
i.e. 1000-2000, given size 1001.
相反，這個就有點欠缺了，需要做一點變形，而且比上面這個慢點，還要考慮overflow。
【在 f*******t 的大作中提到】
: 最优解：
: int findDup(int[] A) {
: int ans = 0;
: for (int i = 0; i < n; i++) {
: ans ^= A[i];
: ans ^= i;
: }
: return ans;
: }
|
c********p
发帖数: 1969 | |
o********7
发帖数: 154 | 36 碰到过一个类似的：
数组只有1-10000，然后size也是10000，因为有一个miss了， 有一个重复了， 怎么找
到miss那个 |
u*****o
发帖数: 1224 | 37 这题也好玩，可以用XOR做吗？
【在 o********7 的大作中提到】
: 碰到过一个类似的：
: 数组只有1-10000，然后size也是10000，因为有一个miss了， 有一个重复了， 怎么找
: 到miss那个
|
a*****e
发帖数: 911 | 38 why need "ans ^= i"?
【在 f*******t 的大作中提到】
: 最优解：
: int findDup(int[] A) {
: int ans = 0;
: for (int i = 0; i < n; i++) {
: ans ^= A[i];
: ans ^= i;
: }
: return ans;
: }
|
s******n
发帖数: 20 | 39 这个程序正确是建立在这个等式成立：ans = (0-n)^(0-n)^dup
这个数学上如何证明呢？
【在 f*******t 的大作中提到】
: 最优解：
: int findDup(int[] A) {
: int ans = 0;
: for (int i = 0; i < n; i++) {
: ans ^= A[i];
: ans ^= i;
: }
: return ans;
: }
|
m****8
发帖数: 60 | 40 这是加减两个操作 如果是公式算 只用减一个操作
【在 G****A 的大作中提到】
: 这个小trick不错
|
|
|
m****8
发帖数: 60 | 41 thats it
【在 f*******t 的大作中提到】
: 最优解：
: int findDup(int[] A) {
: int ans = 0;
: for (int i = 0; i < n; i++) {
: ans ^= A[i];
: ans ^= i;
: }
: return ans;
: }
|
h****p
发帖数: 87 | |
a*****u
发帖数: 1712 | 43 我今天也被面了这道题，我只说了partition的办法，好像比较满意。楼下的办法好牛
【在 c*******r 的大作中提到】
: 数组只有1-10000，然后size是10001，怎么找到重复的那个
: ONSITE题目，让用尽可能多的方法。我能想到的方法是sum之后做减法， Hashtable,
: sorting完扫一边， 或者boolean数组存。
: 当时二逼用了swap的算法不停swap，结果最后自己没弄出来。
: 想问下这题有什么比较好的解法啊？
|
s******n
发帖数: 20 | 44 XOR有下列性质：
XOR is associative, so (x ^ y) ^ z = x ^ (y ^ z)
XOR is commutative: x ^ y = y ^ x
XOR is its own inverse: x ^ y = 0 if x = y
XOR has zero as an identity: x ^ 0 = x
所以 ans = (0-n)^(0-n)^dup = dup
【在 s******n 的大作中提到】
: 这个程序正确是建立在这个等式成立：ans = (0-n)^(0-n)^dup
: 这个数学上如何证明呢？
|
T*****u
发帖数: 7103 | 45 找到m^n和m-n能算出两个来吗？方法比较笨了。
【在 o********7 的大作中提到】
: 碰到过一个类似的：
: 数组只有1-10000，然后size也是10000，因为有一个miss了， 有一个重复了， 怎么找
: 到miss那个
|
k*j
发帖数: 153 | 46 这题是1-10000
而不是从0开始的，
为什么不是
: ans ^= A[i];
: ans ^= (i+1);
??
【在 f*******t 的大作中提到】
: 最优解：
: int findDup(int[] A) {
: int ans = 0;
: for (int i = 0; i < n; i++) {
: ans ^= A[i];
: ans ^= i;
: }
: return ans;
: }
|
u*****o
发帖数: 1224 | 47 你好我想和你讨论一下你的办法。如果我没理解错，m是array, n是INDEX，
如果ARRAY里有 0， 1， 2， 3， 3
他们的index是0，1，2，3，4
m^n结果是 3^4 = 000
m-n 结果是3-4=-1.
知道这两个方程怎么求出3是重复的，4是没出现的呢？
【在 T*****u 的大作中提到】
: 找到m^n和m-n能算出两个来吗？方法比较笨了。
|
x*****0
发帖数: 452 | |
s**********r
发帖数: 8153 | |
c********e
发帖数: 186 | 50 mark
【在 c*******r 的大作中提到】
: 数组只有1-10000，然后size是10001，怎么找到重复的那个
: ONSITE题目，让用尽可能多的方法。我能想到的方法是sum之后做减法， Hashtable,
: sorting完扫一边， 或者boolean数组存。
: 当时二逼用了swap的算法不停swap，结果最后自己没弄出来。
: 想问下这题有什么比较好的解法啊？
|
|
|
z****e
发帖数: 54598 | 51 swap
xor
plus
这种题目真心烂大街 |
s*******n
发帖数: 305 | 52
这个没有问题吗？用上面的code跑了一下， 会出问题呀， 还是我的理解有问题。
findDup({0,1,2,2,3}）=6;
findDup({0,1,2,3,3}) =7;
e.g.:
For {0,1,2,3,3}, when i =4:
ans = ans^A[4] = ans^3= 0^3=3;
ans = ans^i =3^4=7;
【在 f*******t 的大作中提到】
: 最优解：
: int findDup(int[] A) {
: int ans = 0;
: for (int i = 0; i < n; i++) {
: ans ^= A[i];
: ans ^= i;
: }
: return ans;
: }
|
s*******n
发帖数: 305 | 53
....., 又试了这个解法，把long改成int了，可是结果也不一样了。
findDup({0,1,2,2,3}）=-2;
findDup({0,1,2,3,3}) =-1;
e.g.:
For {0,1,2,3,3},
i=0, ret=0-0=0;
i=1, ret=1-1=0;
i=2, ret=2-2=0;
i=3, ret=3-3=0;
i=4, ret=3-4=-1;
是不是我理解力真有问题了，今天不适合做题了。。。
【在 c*******r 的大作中提到】
: O(n). 一个小bug, i<=n
: int findDup(int []a,int n){
: long ret=0;
: for(int i=0;i: ret+=a[i]-i;
: }
: return ret;
: }
|
u*****o
发帖数: 1224 | 54 这题数不能从0开始啊，必须是从1开始，才能保证和下标一个个消掉。
原题是数组只有1-10000，然后size是10001
你的例子的话呢，就是
findDup({1,2,2,3,4})
要用0进数组的话得改一下下标。
【在 s*******n 的大作中提到】
:
: ....., 又试了这个解法，把long改成int了，可是结果也不一样了。
: findDup({0,1,2,2,3}）=-2;
: findDup({0,1,2,3,3}) =-1;
: e.g.:
: For {0,1,2,3,3},
: i=0, ret=0-0=0;
: i=1, ret=1-1=0;
: i=2, ret=2-2=0;
: i=3, ret=3-3=0;
|
s*******n
发帖数: 305 | 55
明白了， 两种解法都是这个问题， 不能从0开始。
多谢多谢！！！
【在 u*****o 的大作中提到】
: 这题数不能从0开始啊，必须是从1开始，才能保证和下标一个个消掉。
: 原题是数组只有1-10000，然后size是10001
: 你的例子的话呢，就是
: findDup({1,2,2,3,4})
: 要用0进数组的话得改一下下标。
|
p****e
发帖数: 183 | 56 应该这样吧
// A[] has (n+1) elements, range: (1...n), only one duplicate
int findDup(int A[], int n) {
int ans = 0;
for (int i = 0; i < n; i++) {
ans ^= A[i];
ans ^= (i+1);
}
ans ^= A[n];
return ans;
}
【在 s*******n 的大作中提到】
:
: 明白了， 两种解法都是这个问题， 不能从0开始。
: 多谢多谢！！！
|
s*******n
发帖数: 305 | 57
我理解的还不够透彻，我trace一下，i+1，好像不对。
{1，1，2，3，4} = 4；
个人觉得要理解上面所提到的， 不要去考虑下标了。
XOR有下列性质：
XOR is associative, so (x ^ y) ^ z = x ^ (y ^ z)
XOR is commutative: x ^ y = y ^ x
XOR is its own inverse: x ^ y = 0 if x = y
XOR has zero as an identity: x ^ 0 = x
所以 ans = (0-n)^(0-n)^dup = dup
【在 p****e 的大作中提到】
: 应该这样吧
: // A[] has (n+1) elements, range: (1...n), only one duplicate
: int findDup(int A[], int n) {
: int ans = 0;
: for (int i = 0; i < n; i++) {
: ans ^= A[i];
: ans ^= (i+1);
: }
: ans ^= A[n];
: return ans;
|
L*******e
发帖数: 114 | 58 I wrote the following methods and ran some testings, it works OK. You need
go through the whole list. In your code, i < n, it never touches the last
element.
/**
* A[] has (n+1) elements, range: (1...n), only one duplicate
* @param a
* @return
*/
public static int findDup(int[] a){
int sum = 0;
for (int i = a.length - 1; i >= 0; i--){
sum += (a[i] - i);
}
return sum;
}
public static int findDup2(int[] a){
int sum = 0;
for (int i = 0; i < a.length; i++){
sum ^= i;
sum ^= a[i];
}
return sum;
}
【在 s*******n 的大作中提到】
:
: 我理解的还不够透彻，我trace一下，i+1，好像不对。
: {1，1，2，3，4} = 4；
: 个人觉得要理解上面所提到的， 不要去考虑下标了。
: XOR有下列性质：
: XOR is associative, so (x ^ y) ^ z = x ^ (y ^ z)
: XOR is commutative: x ^ y = y ^ x
: XOR is its own inverse: x ^ y = 0 if x = y
: XOR has zero as an identity: x ^ 0 = x
: 所以 ans = (0-n)^(0-n)^dup = dup
|
x********i
发帖数: 92 | 59 a[0]^a[1]^.......a[10000]^10001就可以了吧.... |
s*w
发帖数: 729 | 60 没见过能解这种两元方程组的方法
可以用 +xi-i 搞一遍得 xdup-xmiss = a
*xi/i 搞一遍得 xdup/xmiss = b
这个两元方程组总会解吧
【在 u*****o 的大作中提到】
: 你好我想和你讨论一下你的办法。如果我没理解错，m是array, n是INDEX，
: 如果ARRAY里有 0， 1， 2， 3， 3
: 他们的index是0，1，2，3，4
: m^n结果是 3^4 = 000
: m-n 结果是3-4=-1.
: 知道这两个方程怎么求出3是重复的，4是没出现的呢？
|
