从10W个数中随机抽走2个数，求出那两个数是多少
这道题目是从51js论坛上看到的，链接在这里>>
题目大意是：
从1到10w（共10w个数）中随机抽走2个数，然后打乱剩下的数的顺序，问如果从这剩下的数中快速的找出抽走的是哪2个数？
我想这道题目其实还有限制（印象中好像以前见过，忘记在哪了…），例如：
1、控制变量的个数使用（最多不允许超过5个）
2、不允许使用数组变量
3、不允许改变数组的值
出这种题目，一般来讲是让答题者只使用一次循环，时间复杂度控制在O(n)，空间复杂度O(1)。
说明：下文中所指的原数组是指，未被打乱顺序、未被截取的数组
现在的数组，指被抽走2个数且顺序被随机打乱了的数组。
数组的下标从0开始，这里的数(10w个数)应该是从1开始，随便拿走两个
1: var n = 100* 1000;
2: var arr = [];
3:
4: for (var i = 0; i < n ; i++) {
5: arr.push(i + 1);
6: }
7:
8: var num1 = arr.splice(Math.floor(Math.random() * arr.length), 1);
9: var num2 = arr.splice(Math.floor(Math.random() * arr.length), 1);
10:
11: document.write('抽掉数：<br/>第1个数是：' + num1 + '，第2个数是：' + num2 + '<br/><br/>');此时的数组为有序的，当打乱顺序时：
1: //打乱
2: arr.sort(function() {return Math.random() > 0.5;});这里使用了sort，效率是很低的，大量的时间会消耗在此，运行的时候会感觉卡了一下。把0.5调整为大一点的数可以减少排序的计算量，例如0.9
现在的数组应该是：
1: var n = 100* 1000;
2: var arr = [];
3:
4: for (var i = 0; i < n ; i++) {
5: arr.push(i + 1);
6: }
7:
8: var num1 = arr.splice(Math.floor(Math.random() * arr.length), 1);
9: var num2 = arr.splice(Math.floor(Math.random() * arr.length), 1);
10:
11: document.write('抽掉数：<br/>第1个数是：' + num1 + '，第2个数是：' + num2 + '<br/><br/>');
12:
13: //打乱
14: arr.sort(function() {return Math.random() > 0.9;});如果找出这两个数呢？
假设这二个数是x和y，则有如下的公式：
令x + y = b
x * x + y * y = c;
为什么假设 x * y = c 呢？因为不太好计算 x * y，要求 x * y的话，是必会使用 1 * 2 * 3 * 4 * … * 100000 这会超过JavaScript最大的精确整数（可以看51js上的讨论）
用正常数组的每一项的平方和，如：1*1 + 2*2 + 3*3 + 4*4 + … + 20*20 + 21*21 + … + (n-1) * (n-1)
减去现在数组中的每一项的平方和，如：2*2 + 4*4 + 3*3 + … + 15*15 + …
如果缺少x, y，则 x*x + y * y = 正常数组每一项的平方各 - 现在数组的每一项的平方各
则有等式：
x + y = b ①
x*x + y * y = c ②
将x = b – y代入第二个方程式中，可得：
(b - y)*(b - y) + y * y = c
<==>
2y2 – 2by + b2 – c = 0
<==>
y2 – by + (b2 – c)/2= 0
根据一元二次的求根公式，根的差别式：
b2 – 4ac ==> b2- 2(b2 - c) ==> 2c – b2
因为方程一定有两上不相等的实数根，故2c – b2一定大于0
两个根（假设为x1、x2），则它们分别为：
上面方程式的两个实根为：
其中，b为x + y的和，c为x*x + y * y 的和。剩下就是如何求这两个数了：
x + y = 原数组每一项之和 - 现在数组中每一项之和
x*x + y * y = 正常数组每一项的平方各 - 现在数组的每一项的平方各
根据以上分析，代码基本上已经出来了：
1 + 2 + 3 + 4 + … + (n – 2 ) + (n - 1) + n 的求和通项公式为：n * (n + 1) / 2。
1: //找出那两个数
2: var t1 = 0,
3: t2 = 0,
4: t3 = 0,
5: len = arr.length;
6:
7: for (;t3 < n ; t3++) {
8:
9: t2 += (t3 + 1) * (t3 + 1);
10:
11: if (t3 < len) {
12: t1 += arr[t3];
13: t2 -= arr[t3] * arr[t3];
14: }
15: }
16:
17: t3 = (n + 1) * n / 2 - t1;
18:
19: var x1 = (t3 - Math.sqrt(2 * t2 - t3 * t3)) / 2;
20: var x2 = (t3 + Math.sqrt(2 * t2 - t3 * t3)) / 2;综上所述，完成的代码如下：
1: var n = 100* 1000;
2: var arr = [];
3:
4: for (var i = 0; i < n ; i++) {
5: arr.push(i + 1);
6: }
7:
8: var num1 = arr.splice(Math.floor(Math.random() * arr.length), 1);
9: var num2 = arr.splice(Math.floor(Math.random() * arr.length), 1);
10:
11: document.write('抽掉数：<br/>第1个数是：' + num1 + '，第2个数是：' + num2 + '<br/><br/>');
12:
13: //打乱
14: arr.sort(function() {return Math.random() > 0.9;});
15:
16:
17: //找出那两个数
18: var t1 = 0,
19: t2 = 0,
20: t3 = 0,
21: len = arr.length;
22:
23: for (;t3 < n ; t3++) {
24:
25: t2 += (t3 + 1) * (t3 + 1);
26:
27: if (t3 < len) {
28: t1 += arr[t3];
29: t2 -= arr[t3] * arr[t3];
30: }
31: }
32:
33: t3 = (n + 1) * n / 2 - t1;
34:
35: var x1 = (t3 - Math.sqrt(2 * t2 - t3 * t3)) / 2;
36: var x2 = (t3 + Math.sqrt(2 * t2 - t3 * t3)) / 2;
37:
38: document.write('计算得到的两个数是：' + x1 + '，' + x2);在线运行示例：
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd"> <html> <head> <title> new document </title> <meta name="generator" content="editplus" /> <meta name="author" content="" /> <meta name="keywords" content="" /> <meta name="description" content="" /> <meta http-equiv="content-type" content="text/html;charset=utf-8" /> </head> <body> </body> </html> 预览代码