一个算法问题

说有一组数,N个,各不相同,然后把这个数组容易加倍,把里面的数都复制一次放进去,就是2N个
然后随机删除一个数,变成2N-1个,从这里找出那个删除的数(给你的就是2N-1个数,所以不能用2N数的和减2n-1个数的和)
请各位给点思路
方法一定要简单

6个回答

这个就是简单的找出一个出现奇数次的数
全部异或一次就可以了

比如
原数组= {1 3 2 2}
复制后= {1 3 2 2 1 3 2 2}
不管删除哪一个,其余的数都出现偶数字,只有那个被删除的数出现奇数次
由于a^a=0 0^a=a
那么全部异或一次后得到的结果就是被删除的那个数
比如删除最后一个2
那么
1^3^2^2^1^3^2=2

把数据存到一个list中,对其中的元素从头开始和后面的元素比较,若有相等的就删除这两个元素(为了后面的元素比较次数减少),后面依次这个处理,那个删除的数一定就是没有配对的那个。

给一个思路吧,不知道是不是楼主想要的意思:
这N个数是定的,对吧,a1, a2, ,,,, aN, 其和为S(n)
现在是加倍,并去掉某个aK.新的双倍长数组和为S(2n-1)
那直接用S(n)- (S(2n-1) - aK)/2 = aK. (存在唯一的aK)
利用这一特性,
一次遍历,对每一个aK, 用上述等式,如果等式成立,返回aK即可。

复杂度也就是O(2n)

说一下我的理解:
比如这组数是:1 2 3 4 5 6 7 8 9
经过加倍后,变成:
1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
随机删除一个数,假设是3,变成下面两种情况(前一部分,后一部分):
[code="java"]
x(n) 0 n-2 n-1 n
1 2 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
x(n) 0 n-2 n-1 n
1 2 3 4 5 6 7 8 9 1 2 4 5 6 7 8 9[/code]
如果 x(0)==x(n-1)
遍历x(i),如果x(i) != x(n-1+i),则删除的数是 x(n-1+i)
如果 x(0)==x(n)

遍历x(i),如果x(i) != x(n-1+i),则删除的数是 x(i)
上面没有特殊情况(删除的数是第一个或者是最后一个),应该也是这个思路,复杂度小于O(n)

[color=red]不行的,事先不知道那n个数的大小,只给你2n-1个数
而且他们是乱序排的,那2n-1也是乱的,所以感觉都不行 [/color]

可能是我没说明白,和顺序大小都没有关系,关键是:"数组加倍,然后把里面的数都复制一次放进去" 这句怎么理解呢,我的理解:如果一个随机数组1,5,2,9,3
加倍后的数组就应该是 1,5,2,9,3,1,5,2,9,3了,我理解有错误没?

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!