腾讯的面试题，谁来挑战下

修正一下，生成array[n]，然后把array[0]忽略掉，后面的一样。

先排序，然后用二分查找法做，应该比较快
n=10000 第一次查找是5000
if n[4999]=5000
那缺失的3个数字肯定就在后半部分
if n[4999]<5000
证明前面肯定有缺失的数字
以此类推

懒得贴代码了，这个以前写过去掉两个的。时间复杂度o(n),空间复杂度o(1)。
根本不需要排序，但需要解方程。说下去掉两个数的思路遍历数组，求取数组的累加和s, 平方和qs。
用1...10000的累加和减去s, 得到移除两数之和a,
用1...10000的平方和减去qs,得到移除两数之和b,那么解方程就可以了
x1 + x2 = a
x1^2 + x2^2 = b需要用的高中数学中的角坐标变换，和差化积什么的。至于去掉三个数大家可以试试立方和
x1 + x2 + x3 = a
x1^2 + x2^2 + x3 = b
x1^3 + x2^3 + x3^3 = c
方程大家可以任意构造，只要其和不用太大，并且易于求解就可以了

我先抛砖，完成最耗时的第一步。
设减少的3个数分别为x、y、z，3个数的和为b，3个数的平方和为c，3个数的立方和为d。
据题意有下面3个等式联立：
x + y + z = b                          ①
x * x + y * y + z * z = c              ②
x * x * x + y * y * y + z * z * z = d  ③
只要求出了b、c、d，我们就可以把①式两边平方再减去②式得到——
x * y + y * z + x * z = f(a, b, c)            ④
再通过(x + y + z)^3 = x^3 + y^3 + z^3 + ... + 6x * y * z的公式和①②③式代入处理③式得到——
x * y * z = f(a, b, c)                        ⑤
根据①④⑤就能转换成一元三次方程，通过盛金公式（B＾2－4AC<0）求取3个根——也就是被减少的那3个数。
下面求解b、c、d：<script type='text/javascript'>
//生成题意
var arr = [], n = 10000;
for (var i = 0; i < n; i++) {
    arr.push(i + 1);
}
var num1 = arr.splice(Math.floor(Math.random() * arr.length), 1);
var num2 = arr.splice(Math.floor(Math.random() * arr.length), 1);
var num3 = arr.splice(Math.floor(Math.random() * arr.length), 1);
document.write('随机抽掉的3个数是：' + num1 + ' 和 ' + num2 + ' 和 ' + num3 + '<br/><br/>');
arr.sort(function(){return Math.random() > 0.6});//求b、c、d
var t = new Date();
var b = c = d = 0, l = arr.length;   // 设3个数的和、平方和、立方和分别为b、c、d
for (var i = 0; i < n; i ++) {
    b += i + 1;
    c += (i + 1) * (i + 1);
    d += (i + 1) * (i + 1) * (i + 1);
    if (i < l) {
        b -= arr[i];
        c -= arr[i] * arr[i];
        d -= arr[i] * arr[i] * arr[i];
    }
}
t = new Date() - t;
document.write('3个数的和、平方和、立方和是：b='+b+'，'+'c='+c+ '，'+'d='+d+'，'+'共耗时：'+t+'毫秒<br/><br/>')
</script>不知道怎么回事，刚才盛金求解的过程发生了错误，就不贴算式代码了（就是先求A、B、C和θ，再代入公式求解，纯数学计算），明天再检查。

写错“f(a, b, c)”，应该为“f(b, c, d)”，笔误。

运行效率IE很慢，FF和Chrome速度快多了。

var a1=[1,...,997],a2=[0,1,...,10000],a3=[],i,j=0;
for(i=0;i<997;i++)a2[a1[i]]=0;
for(i=1;j<3&&i<=10000;i++)if(a2[i]!=0)a3.push(a2[i]);
alert(a3.toString());

var a1=[1,...,997],a2=[0,1,...,10000],a3=[],i,j=0;
for(i=0;i<997;i++)a2[a1[i]]=0;
for(i=1;j<3&&i<=10000;i++)if(a2[i]!=0){a3.push(a2[i]);j++}alert(a3.toString());

return upsider：你那样效率不行的，测试下下就知道了。如果不考虑效率的话，有更简单的方法。
继续：
x + y + z = b
x^2 + y^2 + z^2 = c
x^3 + y^3 + z^3 = d
上面变换可得——
x + y + z = b
x*y + x*z + y*z = (b^2 - c) / 2
x * y * z = b^3 / 6 + d / 3 - b * c / 2
据伟达定理，x、y、z应该为下面方程的3个根——
r^3 - b * r^2 + r * (b^2 - c) / 2 - (b^3 / 6 + d / 3 - b * c / 2)
前面11楼代码已经算出了b、c、d，代入盛金公式为什么就不行呢？
或许，需要二岔逼近求解上面的一元三次方程？

r^3 - b * r^2 + r * (b^2 - c) / 2 - (b^3 / 6 + d / 3 - b * c / 2) = 0 ???????

借用下11楼的借机数组生成代码 // 生成命题数组
function supplyRandomArray(){
var arr = [], n = 10000;
for (var i = 0; i < n; i++) {
arr.push(i + 1);
}
var num1 = arr.splice(Math.floor(Math.random() * arr.length), 1);
var num2 = arr.splice(Math.floor(Math.random() * arr.length), 1);
var num3 = arr.splice(Math.floor(Math.random() * arr.length), 1);
document.write('随机抽掉的3个数是：' + num1 + ' 和 ' + num2 + ' 和 ' + num3 + '<br/><br/>');
arr.sort(function(){return Math.random() > 0.6});
return arr;
}

// 从数组中找出丢失的元素
function getMissElem(arr){
var result = [], obj = {}, len = arr.length;
for(var i = 0; i < len; i++){
obj[arr[i]] = true;
}
for(var i = 1; i <= len; i++){
if(!obj[i]){
result.push(i);
}
}
return result;
}

var arr = supplyRandomArray(),
missElem = getMissElem(arr);
document.write("丢失的数字为：" + missElem);

BTW：该题目难的不是方法，而是最理想的效率。

效率你自己试试呗<!doctype>
<html>
<head>
</head>
<body>
<script>

// 生成命题数组
function supplyRandomArray(){
var arr = [], n = 10000;
for (var i = 0; i < n; i++) {
arr.push(i + 1);
}
var num1 = arr.splice(Math.floor(Math.random() * arr.length), 1);
var num2 = arr.splice(Math.floor(Math.random() * arr.length), 1);
var num3 = arr.splice(Math.floor(Math.random() * arr.length), 1);
document.write('随机抽掉的3个数是：' + num1 + ' 和 ' + num2 + ' 和 ' + num3 + '<br/><br/>');
arr.sort(function(){return Math.random() > 0.6});
return arr;
}

// 从数组中找出丢失的元素
function getMissElem(arr){
var result = [], obj = {}, len = arr.length;
for(var i = 0; i < len; i++){
obj[arr[i]] = true;
}
for(var i = 1; i <= 10000; i++){
if(!obj[i]){
result.push(i);
}
}
return result;
}

var date = new Date(), arr, missElem;
arr = supplyRandomArray();

document.write("Time start:<br/>");
missElem = getMissElem(arr);
document.write("丢失的数字为：" + missElem + "<br/>");
document.write("time: " + (new Date().getTime() - date.getTime()) + "ms.<br/>");

</script>
</body>
</html>

1到1w的和-剩下的数累加=少了三个数的和，设为n，把n分解，第一轮，1+2+xx，去剩下的数组里找这三个数，找到了就记，找不到下轮找3+4+xx，循环下去。
只是个思路，估计效率堪忧，而且我编不出程序。各位帮着看看

//假设题目给定的数组为A_Array
var len = A_Array.length;
var B_Array = new Array(len + 3);
for (var i = 0; i < len; i++) {
    B_Array[A_Array[i]] = 1;
}
var k = 0;//k为以找到的数的数量
for (var i = 0; i < len + 3; i++) {
    if (k == 3) break;
    if (B_Array[i] == undefined) {
        document.write(i);
        k++;
    }
}

这个效率非常不错，高手firebug 测试结果：随机抽掉的3个数是：7693 和 1224 和 1145<br/><br/>
Time start:<br/>
丢失的数字为：1145,1224,7693<br/>
time: 77ms.<br/>

执行19楼和32楼测试，对比结果如下
随机抽掉的3个数是：3416 和 5398 和 4503
19楼测试Time start:
丢失的数字为：3416,4503,5398
time: 83ms.
32楼测试Time start:
丢失的数字为：0,3416,4503,5398
time: 104ms.32楼代码我吧break去掉了，因为你的方式有点不准确，发现多找到一个0 ，但就效率还是不错的，比19楼稍微差一点点

不知道这样可不可以
          public class DicCount
    {
        int n = 1000;
        ArrayList arr = new ArrayList();
        ArrayList array = new ArrayList();
        Random ram = new Random();        public void Circulate()
        {
            for (int i = 1; i <= n; i++)
            {
                arr.Add(i);
            }
            int m = n;
            for (int j = 1; j <= n - 3; j++)
            {
                array.Add(arr[ram.Next(1, m) - 1]);
                arr.Remove(arr[ram.Next(1, m) - 1]);
                m--;
            }
        }    }

常用B端配置Firefox查找耗时在10ms以下才能通过该面试题，再想想办法。

19楼的代码基本就在10ms以下了，只是时间计算把原来不该包含的生成命题数组那部份也包括进来了才会需要那么长时间。        // 生成命题数组
        function supplyRandomArray(){
            var arr = [], n = 10000;
            for (var i = 0; i < n; i++) {
                arr.push(i + 1);
            }
            var num1 = arr.splice(Math.floor(Math.random() * arr.length), 1);
            var num2 = arr.splice(Math.floor(Math.random() * arr.length), 1);
            var num3 = arr.splice(Math.floor(Math.random() * arr.length), 1);
            document.write('随机抽掉的3个数是：' + num1 + ' 和 ' + num2 + ' 和 ' + num3 + '<br/><br/>');
            arr.sort(function(){return Math.random() > 0.6});
            return arr;
        }

        // 从数组中找出丢失的元素
        function getMissElem(arr){
            var result = [], obj = {}, len = arr.length, count = 0;
            for(var i = 0; i < len; i++){
                obj[arr[i]] = true;
            }
            for(var i = 1; i <= 10000; i++){
             !obj[i] && result.push(i);
            }
            return result;
        }


        var arr = supplyRandomArray();

        document.write("Time start:<br/>");
        var date = new Date(),
         missElem = getMissElem(arr);
        document.write("丢失的数字为：" + missElem + "<br/>");
        document.write("time: " + (new Date().getTime() - date.getTime()) + "ms.<br/>");如果还觉得慢，可以像32楼那样，判断找到3个丢失数字后break也减少循环次数

唉，我那思路是有依据的：如果把n再提高一个数量级从1万增加到10万，从1到n的连续整数中查找到2个随机抽取（后乱序）的方法——<script type="text/javascript">
//生成题意
var n = 100000, arr = [];
for (var i = 0; i < n; i++) {
    arr.push(i + 1);
}
var num1 = arr.splice(Math.floor(Math.random() * arr.length), 1);
var num2 = arr.splice(Math.floor(Math.random() * arr.length), 1);
document.write('随机抽掉两个数：' + num1 + ' 和 ' + num2 + '<br/>');
arr.sort(function(){return Math.random() > 0.6});//解题测试
var t = new Date();
var b = 0, c = 0, l = arr.length;
for (var i = 0; i < n; i ++) {
    b += i + 1;
    c += (i + 1) * (i + 1);
    if (i < l) {
        b -= arr[i];
        c -= arr[i] * arr[i];
    }
}
var x = (b + Math.sqrt(2 * c - b * b)) / 2;
t = new Date() - t;document.write('找到的两个数是：' + x + ' 和 ' + [b - x] + '<br/><br/>');
document.write('寻找两数时间是：' + t + '毫秒');
</script>这样一个循环同步递、加递减规避了JS的大数精度问题，再加上纯数学计算大大提升了运行效率。在FF4.0下测试，耗时在5ms以下。
从前年初至今，我有空的时候陆续试过很多种方法，还木有找到第二种的效率能够与上面思路相比拟——简直数量级的差别，不信可对比测试看看。

这个明显是要用bitmap了用Bitmap时间复杂度O(n)，控空间复杂度O(n)申请一个长度为n的数组bitMap[n]，该数组的类型为bit就行了，也就是一位,数组的值全部初始化为0然后扫描题目给的数组，假设每次从数组中取的数为i，置bitMap[i]=1扫完题中给的数组后，扫一遍bitMap数组，假设遇到置为0的元素，该元素下标的值就是缺少的三个数字不用大量计算，极少空间，只要做两次n的循环，和n次赋值和n次比较

恩判断break写的地方不对，应该直接放到下面的判断里去这样可以少很多次判断
0是我没注意到是1到n 以为是从0开始的

调试易

腾讯的面试题，谁来挑战下

解决方案 »