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)
blank

相关推荐

  • windows系统C#(.Net)MySql数据库同步工具

    windows系统C#(.Net)MySql数据库同步工具DbSyncDbSync是一款使用.Net4.5(可以转Core)作为基础框架开发的,目前运行在windows平台的数据库同步工具。此类工具开源社区有很多,这里不是为了重复造轮子,仅仅是因为公司业务需要,不建议直接在生产环境上使用。项目介绍DbSync运行在windows平台的数据库同步工具支持一主多从同步支持同步方式设设置(结构,索引,增量,全量)支持指定表同步和忽略表同步支持同步计划,定时同步展示信息获取本人QQ:724926089,代码比较简单,有需要支持的地

  • 电脑爱好者2012年全彩高清PDF

    电脑爱好者2012年全彩高清PDF电脑爱好者2012年第01期.pdf电脑爱好者2012年第02期全彩高清PDF免费高速下载.pdf电脑爱好者2012年第03期全彩高清PDF免费高速下载.pdf电脑爱好者2012年第04期全彩高清PD…

  • 100+Python编程题给你练(附答案)

    大家如果能坚持独立思考完成以下题目,一定可以帮大家轻松getPython的编程技能。目前,这个项目已经获得了3994Stars,2952Forks。Github地址:Python-programming-exercises首先,这100+练习题根据难易程度分为三个等级:Level1、2和3。下面对如何定义这三个Level进行了说明,大家可以结合自身的学习能…

  • 关于CommandType.StoredProcedure输出参数访问问题

    关于CommandType.StoredProcedure输出参数访问问题MSDN解释:当您将 Command 对象用于存储过程时,可以将 Command 对象的 CommandType 属性设置为 StoredProcedure。当 CommandType 为 StoredProcedure 时,可以使用 Command 的 Parameters 属性来访问输入及输出参数和返回值。无论调用哪一个 Execute 方法,都可以访问 Parameters 属性。但是,

  • pycharm卸载了环境变量还在怎么办_pycharm使用教程

    pycharm卸载了环境变量还在怎么办_pycharm使用教程因为之前的pycharm是社区版的,有些功能不全,所以需要重装专业版重装pycharm最大的顾虑就是之前的库能否保留以及能否删除干净1.之前的库包卸载之前找到我之前的库包所用编译器,记下路径就行注意:因为python跟pycharm是单独存在的,所以删除的pycharm并没有影响python里安装的库包2.删除正版软件删除是最简单的,找到文件所在位置,直接卸载就行这里注意两个红色箭头要全选,然后等待卸载结束就行。3.重新安装下载链接:http://www.jetbrains.com/

  • SQL Set Language Transact-SQL 設置國家語言

    SQL Set Language Transact-SQL 設置國家語言

发表回复

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

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