shuffle洗牌算法java_洗牌算法shuffle[通俗易懂]

洗牌算法1.背景阿里的面试的时候做的一道笔试题:题目:写一个方法,入参为自然数n(n>0),返回一个自然数数组,数组长度为n,元素为[1,n]之间,且每个元素不重复,数组中各元素顺序要求随机;实例1:输入:N=3输出:132实例2:输入:N=5输出:32514当时我的解法(写了两种方法):写的好烂,面完和面试官交流的时候面试官让我看下Collect…

大家好,又见面了,我是你们的朋友全栈君。

5f86bc314e29

洗牌算法

1.   背景

阿里的面试的时候做的一道笔试题:题目:写一个方法,入参为自然数n  (n > 0),返回一个自然数数组,数组长度为n,元素为[1,n]之间,且每个元素不重复,数组中各元素顺序要求随机;

实例1: 输入: N = 3  输出: 132

实例2: 输入: N = 5   输出: 32514

当时我的解法(写了两种方法):

5f86bc314e29

5f86bc314e29

写的好烂,面完和面试官交流的时候面试官让我看下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实现这段伪代码:

5f86bc314e29

使用ES6实现的

Knuth-Durstenfeld Shuffle

算法需要的时间正比于要随机置乱的数,不需要额为的存储空间开销,时间复杂度为O(n),空间复杂度O(1)。

3.

Collections.shuffle()

源码解析:

5f86bc314e29

shuffle方法的入口

传入待洗牌的List集合,定义一个随机数种子。

5f86bc314e29

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账号...

(0)


相关推荐

  • goland2021.2激活破解(已测有效)

    goland2021.2激活破解(已测有效),https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • cpu后缀讲解

    cpu后缀讲解Intel桌面式CPUX后缀 X代表Extreme,中文意思是至尊级,代表同一时代性能最强的CPU。如Corei7-5960X、Corei7-4960X。X代表在同一代中只有一款CPU黄袍加身,地位至高无上。加上没有竞争对手可以望其项背,从露面都退出市场,期待的弑君者没有出现。SandyBridge时代到现在,竞争的天平一直向Intel倾斜。K后缀自从SandyBridge时代Intel限制

  • 基本介绍LINUX远程PC软件:PUTTY、SecureCRT、X-Manager

    基本介绍LINUX远程PC软件:PUTTY、SecureCRT、X-Manager

  • listlength函数头文件_length函数

    listlength函数头文件_length函数length函数系统默认用户浏览8778请教MySQL高手:“length()”函数与“char_length()”函数的区别是什么?高手,您好:小弟的提问如题。希望高手能够为小弟举出一个能够展示length()函数与char_length()函数区别的例子。并且配合两个函数的作用机理,为小弟做一下这两个函数区别的讲解。谢谢…高手,您好:小弟的提问如题。希望高手能够为小弟举出一个能够展示le…

  • java字符串按照特定字符分割_java 字符串分割

    java字符串按照特定字符分割_java 字符串分割问题描述://把字符串”192.168.1.1″按照小圆点进行分割,分割成”192″,”168″,”1″,”1″四个字符串。StringpreStr=”192.168.1.1″;String[]string=preStr.split(“.”);//错误写法。这种写法得到的字符串组长度为0String[]string=preStr.split(“\\.”);//正确写法。对…

  • 纯c语言写银行家算法

    纯c语言写银行家算法主要参考链接:https://blog.csdn.net/houchaoqun_xmu/article/details/55540792https://liuyanzhao.com/2932.html(这个是额外贴出可以参考的连接。本文的主要参考链接依旧是第一条)[声明]本文为转载是因为代码大多数都是网上copy的,然后自己也只是微调加实现过,个人认为不可以当原创。代码全部都贴上来了,…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号