t*****2
发帖数: 9 | 1 1002个数， 数的范围是1到1000.
找出2个duplicate的数，要求Space O(1) |
c********r
发帖数: 286 | 2 public class FindDuplicatedInt {
public static int FindDup(int[] arr)
{
if(arr.length > 1002 || arr == null) return -1;
int checker = 0;
for(int i = 0;i
int val = arr[i];
if((checker & (1<0){
return val;
}
checker |= (1<
}
return -1;
}
public static void main(String[] args) {
int [] a = new int[]{1,2,3,4,5,6,7,8,9,10,2};
System.out.println(FindDup(a));
}
} |
C***U
发帖数: 2406 | 3 算法和找最小的没有出现的正整数的算法一样
把i放到A[i-1]去，那么A[1000]和A[1001]就是重复的两个数
这样是O(n)时间，O(1)空间
【在 t*****2 的大作中提到】
: 1002个数， 数的范围是1到1000.
: 找出2个duplicate的数，要求Space O(1)
|
s******o
发帖数: 2233 | 4 this is wrong
try any number larger than 32
【在 c********r 的大作中提到】
: public class FindDuplicatedInt {
: public static int FindDup(int[] arr)
: {
: if(arr.length > 1002 || arr == null) return -1;
: int checker = 0;
: for(int i = 0;i: int val = arr[i];
: if((checker & (1<0){
: return val;
: }
|
c********r
发帖数: 286 | 5 还真是，多谢大侠指正。 能解释一下原因吗？我想了一下，没想出为什么
【在 s******o 的大作中提到】
: this is wrong
: try any number larger than 32
|
r*****e
发帖数: 792 | 6 两个重复的数是不一样的还是可能相同？
【在 t*****2 的大作中提到】
: 1002个数， 数的范围是1到1000.
: 找出2个duplicate的数，要求Space O(1)
|
a********d
发帖数: 195 | 7 这么写行么？
public static List getDup(int[] org)
{
List ls= new List();
int length=org.length;
int[] chk= new int[length];
for(int i=0;i
{
int tempt=org[i];
if(arr[tempt]<=0)
{arr[tempt]=tempt;}
else
{ls.add(tempt);}
}//end of for
return ls;
} |
l*****a
发帖数: 14598 | 8 什么叫第1000出现的？
数组如果是1，1，1，2，3，4。。。呢
【在 C***U 的大作中提到】
: 算法和找最小的没有出现的正整数的算法一样
: 把i放到A[i-1]去，那么A[1000]和A[1001]就是重复的两个数
: 这样是O(n)时间，O(1)空间
|
c********r
发帖数: 286 | 9 这个应该没问题了，欢迎大家指正
public static int FindDup2(int[] arr)
{
if(arr.length > 1002 || arr == null) return -1;
boolean[] check = new boolean[1002];
for(int i =0;i
if(check[arr[i]])
{
return arr[i];
}else{
check[arr[i]]=true;
}
}
return -1;
}
public static void main(String[] args) {
int [] a = new int[]{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,
21,22,23,24,25,26,27,28,29,30,31,32,33,34,40,40};
System.out.println(FindDup2(a));
} |
l*****a
发帖数: 14598 | 10 用了多少空间？
【在 c********r 的大作中提到】
: 这个应该没问题了，欢迎大家指正
: public static int FindDup2(int[] arr)
: {
: if(arr.length > 1002 || arr == null) return -1;
: boolean[] check = new boolean[1002];
: for(int i =0;i: if(check[arr[i]])
: {
: return arr[i];
: }else{
|
|
|
C***U
发帖数: 2406 | 11 1，1，1，2，3，4，5.。。。
这个数组
一个1被放在A[0]
2被放在A[1]
3被放在A[2]
以此类推
做完这样以后
两个多余的1会被放在A[1000]和A[1001]
【在 l*****a 的大作中提到】
: 什么叫第1000出现的？
: 数组如果是1，1，1，2，3，4。。。呢
|
j********e
发帖数: 1192 | 12 另一种思路: 假定重复的是x和y,
把1002个数异或，结果应该是 A = x^y,
把1002个数加起来再减去Sum(1..1000),结果是B = x+y
这两个方程应该能解出唯一的x和y吧
【在 t*****2 的大作中提到】
: 1002个数， 数的范围是1到1000.
: 找出2个duplicate的数，要求Space O(1)
|
c********r
发帖数: 286 | 13 O（1)
【在 l*****a 的大作中提到】
: 用了多少空间？
|
x*******1
发帖数: 28835 | 14 A = x^y,
B = x+y
能解出来么？呵呵， willing wish了。 |
x*******1
发帖数: 28835 | 15 不堪题目么， O(1)空间。 A 哪来的？
【在 C***U 的大作中提到】
: 1，1，1，2，3，4，5.。。。
: 这个数组
: 一个1被放在A[0]
: 2被放在A[1]
: 3被放在A[2]
: 以此类推
: 做完这样以后
: 两个多余的1会被放在A[1000]和A[1001]
|
x*******1
发帖数: 28835 | 16 boolean[] check = new boolean[1002];
？？？
【在 c********r 的大作中提到】
: O（1)
|
C***U
发帖数: 2406 | 17 A是数列本身。。。。
用的是这道题目的思想
查找 一个数列中没有出现的最小正整数
那到题目用的O(n）时间 O(1） 空间。
【在 x*******1 的大作中提到】
: 不堪题目么， O(1)空间。 A 哪来的？
|
l*****a
发帖数: 14598 | 18 我不知道你咋做的。
可是我似乎可以看到了三个一就结束了（如果输入正确的话）
【在 C***U 的大作中提到】
: 1，1，1，2，3，4，5.。。。
: 这个数组
: 一个1被放在A[0]
: 2被放在A[1]
: 3被放在A[2]
: 以此类推
: 做完这样以后
: 两个多余的1会被放在A[1000]和A[1001]
|
j********e
发帖数: 1192 | 19 肯定能解，你只要做个loop，x从1到B-1，然后验证 (B-x)^x是否等于A.
问题是，有多个解:(
【在 x*******1 的大作中提到】
: A = x^y,
: B = x+y
: 能解出来么？呵呵， willing wish了。
|
l*****a
发帖数: 14598 | 20 boolean[] check = new boolean[1002];
【在 c********r 的大作中提到】
: O（1)
|
|
|
x*******1
发帖数: 28835 | 21 那肯定要swap了 , 找到然后swap， 那就不是O(n) 算法了。
【在 C***U 的大作中提到】
: A是数列本身。。。。
: 用的是这道题目的思想
: 查找 一个数列中没有出现的最小正整数
: 那到题目用的O(n）时间 O(1） 空间。
|
C***U
发帖数: 2406 | 22 步骤是这样的
第一个遇到1 他放在了A[0] 所以不用变动。
第二个遇到1 然后和A[0]位置对比 发现一样 就不变动
第三个遇到1 然后和A[0]位置对比 发现一样 不动
第四个遇到2 然后放到A[1]上 A[1]上的1放到A[3]
第五个遇到3 依次类推
这样对不对？
【在 l*****a 的大作中提到】
: 我不知道你咋做的。
: 可是我似乎可以看到了三个一就结束了（如果输入正确的话）
|
C***U
发帖数: 2406 | 23 是O(n)时间
你看一下这道题目的算法
http://csjobinterview.wordpress.com/2012/03/22/find-out-the-sma
【在 x*******1 的大作中提到】
: 那肯定要swap了 , 找到然后swap， 那就不是O(n) 算法了。
|
d**e
发帖数: 6098 | 24 他意思应该是说到第三个就结束了，就不需要再比下去了
【在 C***U 的大作中提到】
: 步骤是这样的
: 第一个遇到1 他放在了A[0] 所以不用变动。
: 第二个遇到1 然后和A[0]位置对比 发现一样 就不变动
: 第三个遇到1 然后和A[0]位置对比 发现一样 不动
: 第四个遇到2 然后放到A[1]上 A[1]上的1放到A[3]
: 第五个遇到3 依次类推
: 这样对不对？
|
j********e
发帖数: 1192 | 25 这样swap应该还是O(n),因为一个数只被swap一次就到对应的位置了，
然后loop扫到这个数时，检查一下就跳过这个数了。
【在 x*******1 的大作中提到】
: 那肯定要swap了 , 找到然后swap， 那就不是O(n) 算法了。
|
C***U
发帖数: 2406 | 26 哦 好啊
但是对于一般的情况都应该是O(n)的
常数时间应该是不可能的
【在 d**e 的大作中提到】
: 他意思应该是说到第三个就结束了，就不需要再比下去了
|
l*****a
发帖数: 14598 | 27 if(a[abs(a[i])-1]<0)
{
abs(a[i]) is dup
}
else
{
a[abs(a[i])-1]*=-1;
}
不知到有没有更好的办法
【在 C***U 的大作中提到】
: 步骤是这样的
: 第一个遇到1 他放在了A[0] 所以不用变动。
: 第二个遇到1 然后和A[0]位置对比 发现一样 就不变动
: 第三个遇到1 然后和A[0]位置对比 发现一样 不动
: 第四个遇到2 然后放到A[1]上 A[1]上的1放到A[3]
: 第五个遇到3 依次类推
: 这样对不对？
|
x*******1
发帖数: 28835 | 28 10， 1，9，2，8，3，7，4，6，5
多少次scan 多少次 能 变成
1,2,3,4,5,6,7,8,9,10
【在 j********e 的大作中提到】
: 这样swap应该还是O(n),因为一个数只被swap一次就到对应的位置了，
: 然后loop扫到这个数时，检查一下就跳过这个数了。
:
|
c********r
发帖数: 286 | 29 我想空间复杂度的理解应该是，看运算使用的空间随n的变化而定吧,我的算法无论n=n
或者n=2n, 使用的空间都是一样大，请指正
【在 x*******1 的大作中提到】
: 10， 1，9，2，8，3，7，4，6，5
: 多少次scan 多少次 能 变成
: 1,2,3,4,5,6,7,8,9,10
|
C***U
发帖数: 2406 | 30 8次
加上数组过一遍时间10
总共18 < 2×10
我给你的那个链接你看一下吧
那里有code
应该能看出来时间是O(N)
【在 x*******1 的大作中提到】
: 10， 1，9，2，8，3，7，4，6，5
: 多少次scan 多少次 能 变成
: 1,2,3,4,5,6,7,8,9,10
|
|
|
o*o
发帖数: 5155 | 31 没看懂回帖。有那么复杂吗？
不就是
Sum(n) - Sum(1..1000) = x + y
Sum(n^2) - Sum(1^2..1000^2) = x^2 + y^2
【在 t*****2 的大作中提到】
: 1002个数， 数的范围是1到1000.
: 找出2个duplicate的数，要求Space O(1)
|
C***U
发帖数: 2406 | 32 有那么复杂么。。。要算2次方程
直接把数字放来放去就可以了
【在 o*o 的大作中提到】
: 没看懂回帖。有那么复杂吗？
: 不就是
: Sum(n) - Sum(1..1000) = x + y
: Sum(n^2) - Sum(1^2..1000^2) = x^2 + y^2
|
D****3
发帖数: 611 | 33
其实没多个解。
xy=a,x+y=b;
(x-y)^2=x^2+y^2-2xy=(x+y)^2-4xy=b*b-4a;
x-y= (+/-)sqrt(b*b-4a), 咱就说x-y= +/- k吧
注意，这时候看起来有2个解，其实基于x+y=b, 那么x-y=k和x-y=-k (i.e. y-x=k)是一
样的。因为x和y对称。
不信的话我解一下：
x+y=b, x-y=k --> x=(b+k)/2, y=(b-k)/2
x+y=b, y-x=k --> x=(b-k)/2, y=(b+k)/2
这两个式子的解对称，第一个的x就是第二的y。因为这题里求2个重复数。随便取一个
式子就能算出。
也就是说，两个重复数字分别是(b+k)/2,和(b-k)/2。其中k=sqrt(b*b-4a)。
ps1：我计算可能出点小错误，但是大意应该是对的。
ps2：有人说直接算xy，这样会overflow，想想1*2*...*1000多大吧。不如算1*1+2*2+.
..+x*x+...+y*y+...+1000*1000,这样减去1-1000的平方和，算出来x*x+y*y即可根据x+
y推出xy.
【在 j********e 的大作中提到】
: 这样swap应该还是O(n),因为一个数只被swap一次就到对应的位置了，
: 然后loop扫到这个数时，检查一下就跳过这个数了。
:
|
D****3
发帖数: 611 | 34
这里1000个数字还好，如果是n个数字，放来放去就要O(n) space了吧。
【在 C***U 的大作中提到】
: 有那么复杂么。。。要算2次方程
: 直接把数字放来放去就可以了
|
C***U
发帖数: 2406 | 35 http://csjobinterview.wordpress.com/2012/03/22/find-out-the-sma
这里有解释为什么是O(1)的
【在 D****3 的大作中提到】
:
: 这里1000个数字还好，如果是n个数字，放来放去就要O(n) space了吧。
|
h*****3
发帖数: 1391 | 36 我理解cai的思路就是a[i]= i+1,
所以a[a[i]-1]=a[i];
过一遍以后最后2个值就是dup的了。
这题的思路和leetcode里面那个find missing positive的思路是一样。
没看他的程序，一看程序头就疼。 |
C***U
发帖数: 2406 | 37 你理解对的
我理解cai的思路就是a[i]= i 1,所以a[a[i]-1]=a[i];过一遍以后最后2个值就是dup的
了。这题的思路和leetcode里面那个find missing p........
★ Sent from iPhone App: iReader Mitbbs 7.56 - iPad Lite
【在 h*****3 的大作中提到】
: 我理解cai的思路就是a[i]= i+1,
: 所以a[a[i]-1]=a[i];
: 过一遍以后最后2个值就是dup的了。
: 这题的思路和leetcode里面那个find missing positive的思路是一样。
: 没看他的程序，一看程序头就疼。
|
o*o
发帖数: 5155 | 38 use sum and bit xor:
def printDup(arr, size):
xor = 0
sum = -(1+size-2)*(size-2)/2
for i in range(size):
sum += arr[i]
xor ^= arr[i]
if (i != 0 and i != size-1):
xor ^= i
xor ^= 0
if (xor == 0):
print "x=%s y=%s" % (sum/2, sum/2)
else:
x = 0
least = xor & ~(xor-1)
for i in range(size):
if (arr[i] & least):
x ^= arr[i]
if (i != 0 and i != size-1 and i & least):
x ^= i
x ^= 0
print "x=%s y=%s" % (x, y)
【在 t*****2 的大作中提到】
: 1002个数， 数的范围是1到1000.
: 找出2个duplicate的数，要求Space O(1)
|
h*****3
发帖数: 1391 | 39 我来说说吧，看说的对不对。
rule:a[i]=i+1
a(0)=10,swap a(9),a(0),a(9)=10,a(0)=5
swap a(4),a(0),a(4)=5,a(0)=8
swap a(7),a(0)...until a(0) is 1
check if a( 1) is 2,... 前面swap过的，基本上只是判断而已,因为已经满足了条件。
【在 x*******1 的大作中提到】
: 10， 1，9，2，8，3，7，4，6，5
: 多少次scan 多少次 能 变成
: 1,2,3,4,5,6,7,8,9,10
|
p*****2
发帖数: 21240 | 40
CAIWU是对的吧？
【在 C***U 的大作中提到】
: 算法和找最小的没有出现的正整数的算法一样
: 把i放到A[i-1]去，那么A[1000]和A[1001]就是重复的两个数
: 这样是O(n)时间，O(1)空间
|
|
|
C***U
发帖数: 2406 | 41 需要2爷来认证啊
CAIWU是对的吧？
★ Sent from iPhone App: iReader Mitbbs 7.56 - iPad Lite
【在 p*****2 的大作中提到】
:
: CAIWU是对的吧？
|
g***s
发帖数: 3811 | |
p*****2
发帖数: 21240 | 43
我觉得是对的呀。
【在 C***U 的大作中提到】
: 需要2爷来认证啊
:
: CAIWU是对的吧？
: ★ Sent from iPhone App: iReader Mitbbs 7.56 - iPad Lite
|
p*****2
发帖数: 21240 | 44
去年还没上呀。大牛有什么想法share一下了。
【在 g***s 的大作中提到】
: 这类题去年版上出现了很多次了。
|
g***s
发帖数: 3811 | 45 CAIWU在3楼就给了解法，那就是正解啊。
换i到a[i-1]位置上,最坏情况负责度也就是O(n).
【在 p*****2 的大作中提到】
:
: 去年还没上呀。大牛有什么想法share一下了。
|
o*o
发帖数: 5155 | 46 整个数组的空间都被用了，还是O(1)？这跟拷贝数组有什么区别？
还不如LS贴的对数组元素取负做标志，最后还可以复原数组。
【在 C***U 的大作中提到】
: A是数列本身。。。。
: 用的是这道题目的思想
: 查找 一个数列中没有出现的最小正整数
: 那到题目用的O(n）时间 O(1） 空间。
|
p*****2
发帖数: 21240 | 47
多谢 大牛confirm，我也觉得这是正解。
【在 g***s 的大作中提到】
: CAIWU在3楼就给了解法，那就是正解啊。
: 换i到a[i-1]位置上,最坏情况负责度也就是O(n).
|
s********0
发帖数: 34 | 48 这样行不
如果要找的两个数不一样： a != b
可以转换为 2个(1...1000)的范围 + a + b
即一个数组只有两个数a, b 出现奇数次(3次)，其他均为偶数次(这边为2次),找出a，b
然后按照经典XOR的方法处理 |
