一道面试题：给出1..n的一个排列，其中缺少2个元素，用O(1)的空间找到那2个缺失的元素

本帖最后由 glq2000 于 2010-07-19 14:07 编辑

在 http://hi.baidu.com/huyuanming11 ... 8ace580823021d.html上看到个题目：

给出1..n的一个排列，其中缺少2个元素，用O(1)的空间找到那2个缺失的元素。

就是说不能申请一个大小为N的数组来做这个题。

我想的是可以把1到N加一遍，然后再将现有的数加一遍，两者相减得到 A+B的值(假设确失的两个数是 A和B), 然后同样的办法，
把1到N乘一遍，然后再将现有的数乘一遍，相除得到 A*B的值，这样就求出A和B了，但相乘时肯定会溢出，如果写个处理大数相乘的问题的函数的话，其空间性能肯定不是O（1）， n越大，占用的空间越大。。。。。。。，所以这种方法好像不行。

   那个帖子里说 “只要把全部存在的数xor一边，再和1..n xor 一遍，就转化为M67的问题了” ，不知道他说的“M67”的问题是什么问题，还有，异或两遍之后，可以得到 A与B异或的值，即A^B的值，但是知道A+B的值 和 A^B的值，并不可以唯一确定A和B啊.

比如：如果知道 A+B=C， A xor B= d;

如果c d的值已知， 也不一定能求出A B 啊。

如C=0x 0111, d= 0x0111,

则 A，B的值无法确定。如A = 0X0110, B= 0X0001,
                                    或者A = 0X0101, B= 0X0010, 都是可以的啊，就是说无法唯一的确定A,B。

大家有没有有什么 空间复杂度为O（1）的办法呢？

后来找到个网页， http://www.matrix67.com/blog/archives/511， 是这个问题的一个变形，但解决不了本帖提出的 问题。

第一遍：跟你一样得  A+B = M
第二遍：A*A+B*B = N
解方程

顶 A^2 + B^2 = M 这个办法很不错， 应该能解决溢出的问题。
我查了下平方和的公式  1^2+2^2+3^2+...+n^2=n(n+1)(2n+1)/6 ，在构造A^2 + B^2的过程中，需要计算1^2+2^2+3^2+...+n^2， 这个值的大小在n的三次方附近，
如果n是10000的话，n(n+1)(2n+1)/6 就超出unsigned int的范围了，我想可以改用unsigned long long 来存放这个值，应该不会溢出。

  其实我也不知道标准答案，  A^2 + B^2 = M 这个办法已经很不错了， 但还有没有别的办法呢？