专栏首页游戏杂谈从10W个数中随机抽走2个数,求出那两个数是多少

从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> 预览代码

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【转】flash builder优化方案

    要使用fb进行开发的时候,经常会遇到内存不足,控制台需要退出等问题,还有就是打包生成发布文件的时候,会遇到XX问题而失败…

    meteoric
  • 本机web开发环境的搭建--Apache篇

    和上一篇《本机web开发环境的搭建--nginx篇》一样,这篇也是小白级的文档(大神请忽略~)

    meteoric
  • 命名函数表达式探秘

    本想直接转载过来的,发现效果不太好。而且想起之前好像看过中文,感谢随之漫笔的翻译,它为前端开发作出了不少贡献,很感谢这样的译者。

    meteoric
  • ContentProvider 源码分析

    ContentProvider 启动会伴随进程的启动,在ActivityManagerService中,启动进程是由startProcessLocked方法来完...

    Yif
  • 不定高多行溢出文本省略

    大家应该都知道用text-overflow:ellipsis属性来实现单行文本的溢出显示省略号(…)。当然部分浏览器还需要加宽度width属性。

    空空云
  • Java动态代理之InvocationHandler最简单的入门教程

    版权声明:本文为博主汪子熙原创文章,未经博主允许不得转载。 https://jerry.bl...

    Jerry Wang
  • Java动态代理之InvocationHandler最简单的入门教程

    网上关于Java的动态代理,Proxy和InvocationHandler这些概念有讲解得非常高深的文章。其实这些概念没有那么复杂。现在咱们通过一个最简单的例子...

    Jerry Wang
  • sqlzoo练习7-聚合

    皮大大
  • Syncthing就是我要的同步备份软件

    最开始的时候,我在路由器上开启 Samba,每次编辑完项目就手动拷贝到路由器硬盘里,麻烦程度可想而知,后来又用了 Google Drive/One Drive,...

    气象学家
  • 一次性密码本-绝对不会被破译的密码

    一次性密码本即Vernam Cipher,是由Gilbert Vernam在1917年, 开发的一种加密算法。

    程序那些事

扫码关注云+社区

领取腾讯云代金券