看起来两个函数运行的结论是正确的。
后面的问题,Update确实如上所说的,非常类似,把这些个数字和1-1000异或就得到了答案了。奇数偶数的其实问题的第一二小题分别和迷失一个数字和两个数字对应,想法完全一致,这里不做展开了。
--------------------------------
问题1:
1-N的自然数中,少了一个,找出这个数
O(n)空间的比较简单,下面给出几个个只需要1,2个额外变量的算法
(1)求和-容易溢出
S1=1+2+...+N=(N+1)N/2
然后遍历数列每次从S1中减去当前的数字
最后剩下的数字就是所求
为了防止溢出我们可以每次在S1大于一定的数字后,就去减,然后继续求和,再大于就继续减,以此类推。
(2)异或
Y1=1^2^3...^N
然后遍历数列每次异或当前的数字
最后剩下的就是要求的数字
实际上平时我们用的比较多的互逆运算有 加/减 乘/除 对数/幂数
往往忽略了异或也是有一定的互逆性的
(3)O(N)时间的移动-排序
将a[i]移动到a[a[i]],使得数组有序
然后找出空着的位置
(4)O(NlogN)时间的移动-排序
用快排的思想,在1-N中选取游标X对数组快排一次,如果X被放在a[X-1]的位置上那么,要找的数字在X-N之间
否则X被放在a[X-2]的位置上 要找的数字在1-X-1之间 递归求解,直到找的要找的数字。
问题2:
1-N个自然数,少了两个,找出这两个数
(1)求和-容易溢出
S1=1+2+...+N=(N+1)N/2
S2=1^2+2^2+...+N^2=(N+1)(2N+1)N/6
...
对于少了K个数的情况,如果K很少,我们可以找出K个和上面类似的函数,计算总体值,然后用解K元一次方程得到结果
但要注意函数的选择
(2)异或
按照上面同样的方法,求出最后的值P等于两个数的异或
确定P从低位到高位的第一个1是第i位
现在用快排的思想,将数列分成两个区间A和B
其中A中第i位是0,B中的第i位是1
然后调用问题1中的方法来分别求解A和B
(3)O(N)时间移动-排序
跟上面一样,实际上这种方法对于少了K个数的情况都能适用。
(4)O(NlogN)时间移动-排序
跟上面的方法一样
如果X被放在a[X-1]位置上,要找的两个数字在X-N之间
如果X被放在a[X-2]位置上,要找的数字一个在1-X-1间,一个在X-N之间
如果X被放在a[X-3]位置上,要找的数字都在1-X-1间
对于少了K个数字的情况,这种方法也可以做,但实现起来就比较复杂了
问题3:
给你n个数,其中有且仅有一个数出现了奇数次,其余的数都出现了偶数次。用线性时间常数空间找出出现了奇数次的那一个数。
(1)异或
经过上面的介绍,应该想到异或
一个数跟自己偶数次异或是0
奇数次异或是自己
问题4:
给你n个数,其中有且仅有两个数出现了奇数次,其余的数都出现了偶数次。用线性时间常数空间找出出现了奇数次的那两个数。
看看问题2和3中用异或的方法,应该知道答案了吧?