leecode/daily/2019-07-19.md

毎日一题 - 洗牌算法

信息卡片

• 时间：2019-07-19
• 题目链接：暂无
• tag：Array Probability

题目描述

假设我们有一个n个元素的数组，要求你实现一个函数，该函数会随机地返回n个元素的排列，要求所有排列出现的概率是一样的。即每一个排列出现的概率都是1/n!.

参考答案

思路如下

像洗牌一样，从数组中随机取出一个，放入另一个全新的数组中，但这会涉及到数组删除操作. 在这个基础上转换一下思路把从数组中取出的元素放入原数组中，第一次随机删除时，把它与原数组的倒数第一个交换，第2次在剩下的元素中随机删除时，把它与原数组的倒数第2个交换，第n-1次（最后一次不用换）时便完成了洗牌 时间复杂度为O(n)

	function shuffle(list) {
	  for (let i = list.length - 1; i >= 1; i--) {
	    const random = (Math.random() * (i + 1)) >> 0;
	    const temp = list[i];
	    list[i] = list[random];
	    list[random] = temp;
	  }
	}

注： 概率证明， 任意一个元素放在倒数第一个位置的概率为1/n,放到倒数第2个的概率为 [(n-1)/n ]* [1/(n-1)] = 1/n,放在倒数第k个位置的概率是[(n-1)/n] * [(n-2)/(n-1)] ... [(n-k+1)/(n-k+2)] *[1/(n-k+1)] = 1/n， 因此每一个元素放在任意位置的概率都为1/n,所有的排列出现的概率则为 1/n * 1/(n-1) .. 1 = 1/n!

注：在交换时，之所以第一次与第n个交换不与第一个交换，是因为与第n个交换代码更简洁

优秀解答

暂缺