384. 打乱数组

🟠   🔖  数组 数学 随机化  🔗 力扣 LeetCode

题目

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:

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]

Constraints:

• 1 <= nums.length <= 50
• -10^6 <= nums[i] <= 10^6
• All the elements of nums are unique.
• At most 10^4 calls in total will be made to reset and shuffle.

题目大意

给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。打乱后，数组的所有排列应该是 等可能 的。

实现 Solution class:

• Solution(int[] nums) 使用整数数组 nums 初始化对象
• int[] reset() 重设数组到它的初始状态并返回
• int[] shuffle() 返回数组随机打乱后的结果

示例 1：

输入

["Solution", "shuffle", "reset", "shuffle"]

[[[1, 2, 3]], [], [], []]

输出

[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]

解释

Solution solution = new Solution([1, 2, 3]);

solution.shuffle(); // 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。例如，返回 [3, 1, 2]

solution.reset(); // 重设数组到它的初始状态 [1, 2, 3] 。返回 [1, 2, 3]

solution.shuffle(); // 随机返回数组 [1, 2, 3] 打乱后的结果。例如，返回 [1, 3, 2]

提示：

• 1 <= nums.length <= 50
• -10^6 <= nums[i] <= 10^6
• nums 中的所有元素都是 唯一的
• 最多可以调用 10^4 次 reset 和 shuffle

解题思路

1. 初始化与保存原数组

   • 构造函数中使用 this.origin = nums.slice(); 复制原数组，避免引用同一数组导致不必要的修改。

2. 实现 reset()

   • 使用 slice() 方法返回原数组的副本，确保调用 reset() 不修改原数组。

3. 实现 shuffle()

   • 使用 Fisher-Yates 洗牌算法：
   • 从数组末尾开始遍历数组，每次从未处理部分中随机选择一个数与当前位置交换。
   • 在未处理部分中随机选取一个索引 j，交换当前索引 i 与 j 的值。
   • 返回洗牌后的数组。

复杂度分析

• 时间复杂度:
  • reset(): O(n)
  • shuffle(): O(n)
• 空间复杂度: O(n)，用于保存结果。

代码

/**
 * @param {number[]} nums
 */
var Solution = function (nums) {
	this.origin = nums.slice();
};

/**
 * @return {number[]}
 */
Solution.prototype.reset = function () {
	return this.origin.slice();
};

/**
 * @return {number[]}
 */
Solution.prototype.shuffle = function () {
	const shuffled = this.origin.slice();
	const n = shuffled.length;

	// Fisher-Yates 洗牌
	for (let i = n - 1; i > 0; i--) {
		const j = Math.floor(Math.random() * (i + 1));
		[shuffled[i], shuffled[j]] = [shuffled[j], shuffled[i]];
	}

	return shuffled;
};

/**
 * Your Solution object will be instantiated and called as such:
 * var obj = new Solution(nums)
 * var param_1 = obj.reset()
 * var param_2 = obj.shuffle()
 */