大家好,又见面了,我是你们的朋友全栈君。
洗牌算法
1. 背景
阿里的面试的时候做的一道笔试题:题目:写一个方法,入参为自然数n (n > 0),返回一个自然数数组,数组长度为n,元素为[1,n]之间,且每个元素不重复,数组中各元素顺序要求随机;
实例1: 输入: N = 3 输出: 132
实例2: 输入: N = 5 输出: 32514
当时我的解法(写了两种方法):
写的好烂,面完和面试官交流的时候面试官让我看下Collections.shuffle的源码,于是乎就开始研究这个“洗牌算法”。
2.洗牌算法
洗牌就是将原有的排序打乱的一个过程,我们可以通过抽牌、换牌和插牌三种方式进行洗牌。最常用的洗牌算法:即Fisher-Yates Shuffle和Knuth-Durstenfeld Shhuffle,我们分别学习一下两种洗牌算法。
2.1 Fisher-Yates Shuffle
所述费舍尔-耶茨洗牌是一种算法:用于产生随机排列的有限的序列,简单地说,该算法对序列进行洗牌。
算法的自然语言描述为(给定1到N的序列):①记下从1到N的数字。
②从1到结尾的未删除数字(包括)之间选择一个随机数k。
③从低端开始计数,剔除尚未剔除的第k个数字,并将其写下一个单独的列表的末尾。
④从第2步开始重复,直到所有数字都被删除。
⑤现在在步骤3中写下的数字序列就是原始序列的随机排列。
理论上的费舍尔-耶茨洗牌算法的时间复杂度为O(n²),空间复杂度O(n)。
2.2 Knuth-Durstenfeld Shuffle
所述克努斯-杜斯腾菲尔德算法是一个现代版的费舍尔-耶茨算法,我们实现Fisher和Yates算法时会花费不必要的时间来用来计算上面第3步中的剩余数字,但Durstenfeld的解决方案是将“删除”的数字移到列表的末尾,然后将每个被删除的数字交换为最后一个未删除的数字迭代,简言之:每次迭代时交换这个被取出的数字到原始列表的最后。这将算法的时间复杂度从O(n²)降低到了O(n)。
伪代码实现://To shuffle an arrayaofnelements (indices 0…n-1):
forifromn−1down to1do
j← random integer such that 0 ≤j≤iexchangea[j] anda[i]
按照上述的伪代码的描述,我们使用JS实现这段伪代码:
使用ES6实现的
Knuth-Durstenfeld Shuffle
算法需要的时间正比于要随机置乱的数,不需要额为的存储空间开销,时间复杂度为O(n),空间复杂度O(1)。
3.
Collections.shuffle()
源码解析:
shuffle方法的入口
传入待洗牌的List集合,定义一个随机数种子。
shuffle的具体实现
获取集合的长度,其中SHUFFLE_THRESHOLD = 5,当list的长度<5或者list实现了RandomAccess接口的时候,通过倒序的循环交换索引位置与随机生成的[0,i)的索引位置。
当集合长度>5的时候,将集合转为数组,然后再次进行随机值交换,然后将数组重新set到集合里面去,这样做避免了将“顺序访问”列表洗牌到适当的位置而导致的二次行为。
主意事项:
1)用List list=ArrayList(Arrays.asList(ia)),用shuffle()打乱不会改变底层数组的顺序。
2)用List list=Arrays.aslist(ia),然后用shuffle()打乱会改变底层数组的顺序。
可以使用洗牌算法实现扫雷。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/126128.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...