欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

前端面试(算法篇) - 数组乱序

程序员文章站 2023-10-31 18:28:34
一、面试题 问:有一个长度为 100 的数组,如何从中随机挑选 50 个元素,组成一个新的数组? 答:这个...那个...emmmmmm 问:那先不挑 50 个,就挑一个数,知道怎么做吗? 答:这个我知道!随机生成一个 0 ~ 99 的数,然后去原数组取对应位置的元素就可以了~ 问:好,回到最初的 ......

一、面试题

问:有一个长度为 100 的数组,如何从中随机挑选 50 个元素,组成一个新的数组?

答:这个...那个...emmmmmm

问:那先不挑 50 个,就挑一个数,知道怎么做吗?

答:这个我知道!随机生成一个 0 ~ 99 的数,然后去原数组取对应位置的元素就可以了~

let randomindex = arr[math.floor(math.random() * arr.length)];

问:好,回到最初的问题,怎么挑选 50 个元素?

答:我知道了,在 0 ~ 99 的范围内,随机生成 50 个不重复的数字!

问:是这个思路,具体的实现呢?记得保证效率哦。

答:(吧啦吧啦吧啦)

问:现在假设数组的元素都是 string 类型,如果要把这个数组元素的顺序打乱,有什么办法么?

答:数组的 sort() 方法可以传入一个函数作为参数,这个函数的返回值可以决定排列顺序。在这个函数中写一个随机数,然后就能乱序了。

问:这是一个思路,但这只是伪随机。

答:啊咧?

问:听说过“洗牌算法”吗?

 

二、随机取数

按照上面随机挑选一个数的思路,从原数组中随机抽取一个数,然后使用 splice 删掉该元素

function getrandomarrelement(arr, count) {
    let res = []
    while (res.length < count) {
        // 生成随机 index
        let randomidx = (math.random() * arr.length) >> 0;
        // splice 返回的是一个数组
        res.push(arr.splice(randomidx, 1)[0]);
    }
    return res
}

上面生成随机 index 用到了按位右移操作符 >> 

当后面的操作数是 0 的时候,该语句的结果就和 math.floor() 一样,是向下取整

但位操作符是在数值表示的最底层执行操作,因此速度更快

// 按位右移
(math.random() * 100) >> 0

// math.floor
math.floor(math.random() * 100)

/* 这两种写法的结果是一样的,但位操作的效率更高 */

 

三、通过 sort 乱序

首先认识一下 array.prototype.sort()

这个方法可以传入一个参数 comparefunction,这个参数必须是函数

同时 sort() 会暴露出 array 中的两个元素 (a, b) 作为参数传给 comparefunction

sort() 会根据 comparefunction(a, b) 的返回值,来决定 a 和 b 的相对位置:

  • 如果 comparefunction(a, b) 小于 0 ,那么 a 会被排列到 b 之前;
  • 如果 comparefunction(a, b) 大于 0 ,那么 b 会被排列到 a 之前;
  • 如果 comparefunction(a, b) 等于 0 , a 和 b 的相对位置不变(不稳定!)

根据以上规则,可以在 comparefunction 中生成一个随机数,然后根据随机数做运算,返回一个正负未知的 number,从而实现乱序

function randomsort(a,b) { 
    return .5 - math.random(); 
}

let arr = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'];
arr.sort(randomsort);

但这并不是真正的乱序,计算机的 random 函数因为循环周期的存在,无法生成真正的随机数

 

四、fisher–yates shuffle 洗牌算法

洗牌算法的思路是:

先从数组末尾开始,选取最后一个元素,与数组中随机一个位置的元素交换位置

然后在已经排好的最后一个元素以外的位置中,随机产生一个位置,让该位置元素与倒数第二个元素进行交换

以此类推,打乱整个数组的顺序

function shuffle(arr) {
  let len = arr.length;

  while (len) {
    let i = (math.random() * len--) >> 0;
// 交换位置 let temp = arr[len]; arr[len] = arr[i]; arr[i] = temp; } return arr; }

再结合 es6 的解构赋值,使用洗牌算法就更方便了:

array.prototype.shuffle = function() {
    let m = this.length, i;
    while (m) {
        i = (math.random() * m--) >>> 0;
        [this[m], this[i]] = [this[i], this[m]]
    }
    return this;
}

 

五、用洗牌算法随机取数

再回到从长度为 100 的数组中取 50 个数的问题

之前用的是 splice 修改原数组,如果结合洗牌算法,又会有别的思路

最好是自己先思考一下,然后再展开代码进行比较

前端面试(算法篇) - 数组乱序
function getrandomarrelement(arr, count) {
    let shuffled = arr.slice(0), 
        i = arr.length, 
        min = i - count, 
        temp, 
        index;
    while (i > min) {
        index = math.floor((i--) * math.random());
        temp = shuffled[index];
        shuffled[index] = shuffled[i];
        shuffled[i] = temp;
    }
    return shuffled.slice(min);
}
用洗牌算法从数组中随机取数

 

最后放个彩蛋,关于两种随机取数的性能孰优孰劣

我用 array.form 生成了一个长度为一百万的数组,然后从中随机取十万个数

首先是使用 splice 的方案:

前端面试(算法篇) - 数组乱序

 然后是洗牌算法:

前端面试(算法篇) - 数组乱序

喵喵喵?!! 

 

 

参考资料:

《how to randomize (shuffle) a javascript array?》