从10W个数中随机抽走2个数,求出那两个数是多少-阿里云开发者社区

开发者社区> 开发与运维> 正文

从10W个数中随机抽走2个数,求出那两个数是多少

简介: 这道题目是从51js论坛上看到的,链接在这里>> 题目大意是: 从1到10w(共10w个数)中随机抽走2个数,然后打乱剩下的数的顺序,问如果从这剩下的数中快速的找出抽走的是哪2个数?   我想这道题目其实还有限制(印象中好像以前见过,忘记在哪了…),例如: 1、控制变量的个数使用(最多不允许超过5个) 2、不允许使用数组变量 3、不允许改变数组的值   出这种题目,一般来讲是让答题者只使用一次循环,时间复杂度控制在O(n),空间复杂度O(1)。

这道题目是从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),则它们分别为:

下载

 

上面方程式的两个实根为:

clip_image002

其中,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);

 

 

在线运行示例:

new document

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
开发与运维
使用钉钉扫一扫加入圈子
+ 订阅

集结各类场景实战经验,助你开发运维畅行无忧

其他文章