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

摘要:
数组的下标从0开始。这里的数字应该从1开始。随机取两个1:varn=100*1000;2: vararr=[];3: 4:对于{5:arr.push(i+1);6:}7:8:varnum1=arr.splice;9: varnum2=arr.splice;10: 11:document.write;此时,阵列已排序。当顺序无序时:1://无序2:arr.sort;这里使用排序,效率很低。这里将花费大量时间。跑步时会感觉卡住。

这道题目是从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);

在线运行示例:

免责声明:文章转载自《从10W个数中随机抽走2个数,求出那两个数是多少》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇PHP 图片验证码的问题Flex调整文本的距离下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

相关文章

Linq to sql学习之查询句法

select 描述:查询顾客的公司名、地址信息 查询句法: var构建匿名类型1 =fromcinctx.Customers selectnew { 公司名= c.CompanyName, 地址= c.Address }; 对应SQL: SELECT [t0].[CompanyName], [t0].[Address] FROM [dbo].[...

C99规范

1. 增加restrict指针    C99中增加了公适用于指针的restrict类型修饰符,它是初始访问指针所指对象的惟一途径,因此只有借助restrict指针表达式才能访问对象。restrict指针指针主要用做函数变元,或者指向由malloc()函数所分配的内存变量。restrict数据类型不改变程序的语义。    如果某个函数定义了两个re...

oracle uuid/GUID 主键与number主键比较

记录数:349408 共三个表:T2,T3,T4 T2的ID是RAW(16) T3的ID是char(32) T4的ID是Number 其它字段一样(连ID共22个字段): X1NUMBERX2NUMBERX3VARCHAR2(500 BYTE)X4VARCHAR2(2000 BYTE)X5VARCHAR2(500 BYTE)X6NUMBERX7DATEX8V...

js随机生成一个数组中的随机字符串以及更新验证码

随机生成m,n范围的值得公式: Math.random()*(n-m)+m; 改正公式:Math.random()*(n+1-m)+m // 生成随机字符串function randomMixed(n) {var chars = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B',...

JavaScript-基础知识

一、JavaScript-简介 Web前端有三层: HTML:从语义的角度,描述页面结构 CSS:从审美的角度,描述样式(美化页面) JavaScript:从交互的角度,描述行为(提升用户体验) JavaScript历史背景介绍 布兰登 • 艾奇(Brendan Eich,1961年~),1995年在网景公司,发明的JavaScript。 开...

RobHess的SIFT代码解析之RANSAC

平台:win10 x64 +VS 2015专业版 +opencv-2.4.11 + gtk_-bundle_2.24.10_win32 主要参考:1.代码:RobHess的SIFT源码:SIFT+KD树+BBF算法+RANSAC算法 2.书:王永明 王贵锦 《图像局部不变性特征与描述》 RobHess的SIFT源码中的几个文件说明? RobHes...