原生JS | 随机抽取不重复的数组元素 —— 有没有更好的方法?

HTML5学堂-码匠:从数组中随机抽取不重复的元素,构成新数组,拥有多种方法,来看看你用的方法性能如何?

效果的功能需求

从一个数组当中,随机抽取数个元素,构成新数组,要求这些元素不能重复。(即随机获取不重复的数组元素)

相关说明:在此处依照“构思难度”和“性能”两方面出发,提供了四种不同的实现方法。

方法1:较为“传统”的实现方法

基本实现思路

从第二次随机抽取的元素开始,需要将抽取的元素与当前新数组的已抽取元素相比较,如果相同,则重新抽取,并再次执行比较的操作。

代码实现

var arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
var arrNum=[];
var ranNum = 5;
for(var i = 0; i < ranNum; i++) {
    arrNum[i] = Math.floor(Math.random() * 10);
    if(i > 0) {
        for(var j = 0; j < i; j++) {
            if(arrNum[j] == arrNum[i]) {
                i--;
                break;
            }
        }
    }
}

方法实现难度与执行效率分析

在代码编写方面,涉及循环语句和条件语句的多层嵌套,这种方法比较容易想到,但编写复杂度较高,执行效率上来说很低,随着元素的抽取,要比较的次数越来越多,“失败的抽取”概率越来越大,整体效率低下。

方法2:标记法 / 自定义属性法

基本实现思路

当获取新元素时,为该元素添加一个属性标记,再抽取一个元素之后,先判断是否有属性标记,如果已被标记,则说明该元素已被抽取,此时重新抽取。

代码实现

var arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
var ranNum = 5;
var hash = {};
var result = [];
while(ranNum > 0) {
    var ran = Math.floor(Math.random() * arr.length);
    if (!hash[ran]) {
        hash[ran] = 1;
        result.push(ran);
        ranNum--;
    };
}

方法实现难度与执行效率分析

和第一种方法相比,编写复杂度较低,只需要使用循环语句和条件语句配合即可实现,节省了第一种方法中依次比较的步骤,但依旧存在“失败抽取”的现象,而且失败抽取的概率没有发生任何变化。

方法3:交换法

第三种方法是自己最喜欢的(“交换法”的名字是自己起的),也是自己在使用的。

基本实现思路

该方法的基本原理是,在抽取一个元素之后,将该元素与数组末端的最后一个元素交换,然后将数组最后一个元素扔掉。

随着比较的进行,每次被抽取的元素都被交换到了数组末端,再被扔掉,数组长度也越来越短。

方法实现难度与执行效率分析

这种方法不太容易想到,但它的编写复杂度是三者中最低的,而性能也是最好的,由于每次比较之后,都将已抽取的元素删除了,因此并不会出现失败的抽取,更不需要做什么比较了。

实现思路演示

代码实现 - 第一步

var arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
var result = [ ];
var ranNum = 5;
for (var i = 0; i < ranNum; i++) {
    var ran = Math.floor(Math.random() * arr.length);
    result.push(arr[ran]);
    var center = arr[ran];
    arr[ran] = arr[arr.length - 1];
    arr[arr.length - 1] = center;
    arr = arr.slice(0, arr.length - 1);
};

代码实现 - 优化

仔细观察第一步的代码中,有哪些步骤是不必须的?

交换法中,最重要的是两个点,第一,每次当前元素会被数组末尾元素所替代。第二,每次随机数的范围越来越小,数组长度越来越短。

也就是说,我们只要保证当前元素被末尾元素替代,并不断减小随机数范围,“数组长度”和“数组末尾的元素值”是可以忽略的。

去掉“数组长度”的控制,并且稍加修改代码,就变成了这样:

var arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
var result = [ ];
var ranNum = 5;
for (var i = 0; i < ranNum; i++) {
    var ran = Math.floor(Math.random() * (arr.length - i));
    result.push(arr[ran]);
    var center = arr[ran];
    arr[ran] = arr[arr.length - i - 1];
    arr[arr.length - i - 1] = center;
};

之后,我们取消“处理数组末尾的元素”,代码会得到进一步优化(优化后的代码如下)。

优化后的成品代码

var arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
var result = [ ];
var ranNum = 5;
for (var i = 0; i < ranNum; i++) {
    var ran = Math.floor(Math.random() * (arr.length - i));
    result.push(arr[ran]);
    arr[ran] = arr[arr.length - i - 1];
};

优化后的实现逻辑

方法4:随用随删

基本实现思路

利用splice方法,将抽取到的元素从数组当中删除掉,并利用splice方法返回值,将抽取到的元素存储(push)到结果数组当中。

代码实现

var arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
var result = [];
var ranNum = 5;
for (var i = 0; i < ranNum; i++) {
    var ran = Math.floor(Math.random() * arr.length);
    result.push(arr.splice(ran, 1)[0]);
};

方法实现难度与执行效率分析

该方法和第三种方法类似,但在实现方式上有所不同,也很快捷方便,每次抽取只需要进行截取和“抽取元素”的存取即可。并不会有重复的“失败抽取”和比较。

额外要说的

为何要那么重点讲解第三种方法呢?

一方面是因为第三种和第四种方法性能更好,另一方面是因为第三种方法和下周的活动有关!!!至于啥活动嘛~~~敬请期待吧!

原文发布于微信公众号 - HTML5学堂(h5course-com)

原文发表时间:2017-05-13

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏人工智能LeadAI

查找排序数组的最小值(js)

在由小到大已排序的未知数组中,以某个元素为支点旋转(好比将序列沿着前后顺序围成环移动)得到了一个数组,请找出该数组的最小值。比如倘若原数组(对我们而言,并不知道...

1054
来自专栏前端架构

原码, 反码, 补码-减法变加法-同余理论:详解

一个数在计算机中的二进制表示形式,  叫做这个数的机器数。机器数是带符号的,在计算机用一个数的最高位存放符号, 正数为0, 负数为1.

531
来自专栏Golang语言社区

解决连通性问题的四种算法

连通性问题 问题概述 先来看一张图: ? 在这个彼此连接和断开的点网络中,我们可以找到一条 p 点到 q 点的路径。在计算机网络中判断两台主机是否连通、在社交网...

3889
来自专栏Java Edge

二分查找复杂度分析实战演练

3288
来自专栏玄魂工作室

面试题解:输入一个数A,找到大于A的一个最小数B,且B中不存在连续相当的两个数字

昨天发的算法有一处情况没考虑到,比如加一后有进位,导致又出现重复数字的情况,修正后今天重新发一次。

461
来自专栏算法channel

直接选择排序到堆排序做的那些改进

主要推送关于对算法的思考以及应用的消息。坚信学会如何思考一个算法比单纯地掌握100个知识点重要100倍。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎...

2637
来自专栏猿人谷

二分查找法的实现和应用汇总

在学习算法的过程中,我们除了要了解某个算法的基本原理、实现方式,更重要的一个环节是利用big-O理论来分析算法的复杂度。在时间复杂度和空间复杂度之间,我们又会更...

1876
来自专栏算法channel

归并排序算法的过程图解

主要推送关于对算法的思考以及应用的消息。坚信学会如何思考一个算法比单纯地掌握100个知识点重要100倍。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎...

33111
来自专栏Java技术

Java程序员需要掌握的8大排序算法

在要排序的一组数中,假设前面(n-1)[n>=2] 个数已经是排好顺序的,现在要把第n个数插到前面的有序数中,使得这 n个数也是排好顺序的。如此反复循环,直到全...

593
来自专栏猿人谷

二分查找法的实现和应用汇总

在学习算法的过程中,我们除了要了解某个算法的基本原理、实现方式,更重要的一个环节是利用big-O理论来分析算法的复杂度。在时间复杂度和空间复杂度之间,我们又会更...

1915

扫描关注云+社区