前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >那些代码量很少却很牛X算法——洗牌算法

那些代码量很少却很牛X算法——洗牌算法

作者头像
Android扫地僧
发布2020-03-19 16:03:17
3240
发布2020-03-19 16:03:17
举报
文章被收录于专栏:Android进阶

首先,出一个简单的题目:有一个大小为100的数组,里面的元素是从 1 到 100,怎样随机从里面选择 1 个数呢?

很简单,利用 `Math.random() * 100` ,就可以拿到一个 0 到 99 的随机数,然后去数组找对应的位置就行了。

下面难度提高一点哈! 有一个大小为100的数组,里面的元素是从 1 到 100,怎样随机从里面选择 50 个数呢?注意!不能重复。

如果根据上面的思路,你一定想到了:是不是随机 50 次就行了?

那么问题来了,这 50 次你是不能保证都是不能重复的,对吧!

嗯,你是不是又有灵感了,弄一个数组,把每一次随机的数都放到数组里,下一次随机就看这个数组里面有没有这数,有的话就继续随机,直到这个数组里面有 50 个数字就停止。完美!

嗯,讲道理的话,这样做也没有问题,肯定可以实现题目要求。但是如果我们想一下,就会发现问题:如果我们考虑极限,就比如拿 99 个数字(你不要跟我说:那就考虑相反的情况,拿 1 个数字,把这个数字去掉就行>。< ),是不是越往后重复的概率越高,那么需要重复随机的次数也越大?

是的,小老弟,你很聪明,一下子就理解了。我们可以看下代码:

代码语言:javascript
复制
var idxArr = []
while(idxArr.length < 99){
	let idx = parseInt(Math.random()*100)
	var time = 0
	while(idxArr.includes(idx)) {
		idx = parseInt(Math.random()*100)
		console.log('time', time++)
	}
	idxArr.push(idx);
}

代码很简单,如果随机的数字不在数组里面,就 push 进去,否则就重新随机。这里用了一个 times 来计算每一个数需要随机的次数。可以看下输出:

可以看到,一开始基本是没有重复的,但是到了后面最后一个,要拿到一个没有出现过的随机数需要多达 65 次。

如果你把数组再放大一点,结果会更加夸张。当然,现实里不会有这么极端的情况,就像你说的,要拿 99 个数就反过来剔除 1 个数就行了。但是呢,就算没有 99 也可能有 50 对吧,这个性质还是一样的,就是可能重复较多。

这个时候就需要换一个思路,如果先将数组里面的元素打乱,那么按顺序选择前 50 个不就可以了?

是的!

但我们得注意什么叫乱?

一副扑克有 54 张牌,有 54! 种排列方式。所谓的打乱指的是,你所执行的操作,应该能够 等概率地生成 这 54! 种结果中的一种。

所以呢,进入主题了:洗牌算法。

原理很简单:最后一个数和前面任意 n-1 个数中的一个交换,然后倒数第二个数和前面任意 n-2 个数中的一个交换。。。依次下去就行了。

直接看代码:

代码语言:javascript
复制
public void shuffle(int[] array) {
    int length = array.length;
    Random random = new Random();
    int temp;
    while (length > 0) {
        int index = random.nextInt(length);
        temp = array[index];
        array[index] = array[length -1];
        array[length -1] = temp;
        length--;
    }
}

//[1,2,3,4,5,6,7,8,9]
//输出[6 1 7 8 5 2 4 9 3 ]

在整个过程中,这个算法保证了每一个元素出现在每一个位置的概率是相等的。

这个算法真的很牛逼很经典,而且代码很少。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-02-18,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 Android扫地僧 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档