打乱数组
难度:
标签:
题目描述
给你一个整数数组 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-106 <= nums[i] <= 106nums中的所有元素都是 唯一的- 最多可以调用
104次reset和shuffle
代码结果
运行时间: 62 ms, 内存: 19.6 MB
/*
* This implementation uses Java Stream to achieve a similar functionality.
* Note: Streams are not ideal for this problem since we need to modify the array in place.
* However, we'll use it for demonstration purposes.
*/
import java.util.Arrays;
import java.util.Random;
import java.util.stream.IntStream;
public class SolutionStream {
private int[] original;
private Random rand;
public SolutionStream(int[] nums) {
this.original = nums.clone();
this.rand = new Random();
}
// Resets the array to its original configuration and returns it
public int[] reset() {
return original.clone();
}
// Returns a random shuffling of the array
public int[] shuffle() {
int[] array = original.clone();
IntStream.range(0, array.length).forEach(i -> {
int j = rand.nextInt(i + 1);
int temp = array[i];
array[i] = array[j];
array[j] = temp;
});
return array;
}
}
解释
方法:
这个题解的主要思路是实现一个打乱数组的算法，同时允许随时将数组重置为原始状态。初始化时，存储原始数组的一个副本。重置功能只需返回这个原始副本。打乱功能则通过Fisher-Yates洗牌算法来实现，这个算法通过遍历数组，并在当前位置与后续位置（包括当前位置自身）中随机选择一个进行交换，从而确保每个元素随机出现在任何位置。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
Fisher-Yates洗牌算法如何确保每个元素等可能地出现在任何位置？
▷🦆
在`shuffle()`方法中使用`random.randrange(i, n)`生成随机索引时，是否考虑了所有元素的均匀随机性？
▷🦆
为什么在`shuffle()`方法中要交换当前索引`i`和随机索引`idx`的值，而不是直接将随机索引的元素移动到当前位置？
▷