从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 条评论
登录 后参与评论

相关文章

来自专栏业余草

jQuery实现网页右下角悬浮层提示

最近有同事提到类似网页右下角的消息悬浮提示框的制作。我之前也做过一个类似的例子,很简单。是仿QQ消息。现在感觉之前的那个例子只是说了实现原理,整体上给你的感觉还...

28320
来自专栏程序人生2.0

在WordPress 5.x 中把 HTML 转换成 Markdown 编写文件

即使在 WordPress 5 启用新的 Gutenberg 编辑器之后,很多 Markdown 的插件都失效了。因为不支援到最新的 WordPress 5。

39130
来自专栏业余草

使用easydrag实现可拖动的DIV弹出框

最近在工作中遇到了jquery的easydrag插件,我有一种相见恨晚的赶脚!easydrag极大的方法我们实现div弹框这个...

19460
来自专栏伟大程序猿的诞生

微信小程序开发--【Hello World 及代码结构】(二)

通过上一篇我们已经完成了注册及开发环境的搭建,今天我们来开发我们的第一个微信小程序 微信小程序开发注册流程

28070
来自专栏业余草

Ext实现滚动条一直处于底部的方法

在我们的实际开发应用中,经常会使用到ext的常用控件textarea。对于一些form表单,录入信息的备注,简介等等信息较多的时候就会使用的textarea。最...

24230
来自专栏业余草

分享一款jQuery全屏滚动页面特性案例

分享一款jQuery全屏滚动页面特性案例。 我们在来往官网,或者小米官网都会看到全屏滚动页面的一些例子。可以说全屏滚动页面...

35130
来自专栏业余草

二维码在线生成工具

二维码在生活中使用的场景越来越多!支付宝,微信扫描付等。今天为大家展示一款使用jQuery.qrcode插件制作二维码的方法和工具!

80120
来自专栏业余草

web版pdf在线阅读器

最近论坛里有人提到了,在线pdf阅读器怎么做。我百度了一下,发现很多人都很懒,程序员都很懒吗? 答案是否定的。为什么都不愿...

90910
来自专栏业余草

网页固定侧栏的做法

固定侧边的做法有很多种,今天为大家介绍一种非常简单的做法。整个html文档只有23行代码就搞定了。

30220
来自专栏业余草

HTML5 Canvas API详解

HTML5 是一个新兴标准,它正在以越来越快的速度替代久经考验的 HTML4。HTML5 是一个 W3C “工作草案” — ...

54520

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励