子寒的博客
0%

leetcode384 Shuffle an Array 解题报告

发表于 分类于

英文原题

Given an integer array nums, design an algorithm to randomly shuffle the array. All permutations of the array should be equally likely as a result of the shuffling.

Implement the Solution class:

Solution(int[] nums) Initializes the object with the integer array nums. int[] reset() Resets the array to its original configuration and returns it. int[] shuffle() Returns a random shuffling of the array.

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
Input
["Solution", "shuffle", "reset", "shuffle"]
[[[1, 2, 3]], [], [], []]
Output
[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]

Explanation
Solution solution = new Solution([1, 2, 3]);
solution.shuffle();    // Shuffle the array [1,2,3] and return its result.
                       // Any permutation of [1,2,3] must be equally likely to be returned.
                       // Example: return [3, 1, 2]
solution.reset();      // Resets the array back to its original configuration [1,2,3]. Return [1, 2, 3]
solution.shuffle();    // Returns the random shuffling of array [1,2,3]. Example: return [1, 3, 2]

分析

    这道题目可以直接用random.shuffle()这个方法解决，记录这道题主要是因为学到了一个新的打乱序列方法。     Fisher-Yates洗牌： 具体步骤如下：

  1. 写下从 1 到 N 的数字
  2. 取一个从 1 到剩下的数字（包括这个数字）的随机数 k
  3. 从低位开始，得到第 k个数字（这个数字还没有被取出），把它写在独立的一个列表的最后一位
  4. 重复第 2步，直到所有的数字都被取出
  5. 第 3 步写出的这个序列，现在就是原始数字的随机排列 已经证明如果第 2 步取出的数字是真随机的，那么最后得到的排序一定也是。

python 代码

这里就只有shuffle部分的代码：

1
2
3
4
5
6
def shuffle(self):
	nums_s = self.nums[:]
	for i in range(len(nums)):
		random_num = random.randrange(i, len(nums))
		nums_s[i], nums_s[random_num] = nums_s[random_num], nums_s[i]
	return nums_s