摄影网站源代码,体验营销理论,武功县住房和城乡建设局网站,导航网源码一、题目描述
给你一个整数数组 nums #xff0c;设计算法来打乱一个没有重复元素的数组。打乱后#xff0c;数组的所有排列应该是 等可能 的。
实现 Solution class:
Solution(int[] nums) 使用整数数组 nums 初始化对象int[] reset() 重设数组到它的初始状态并返回int[]…一、题目描述
给你一个整数数组 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^6nums 中的所有元素都是 唯一的最多可以调用 10^4 次 reset 和 shuffle
二、解题思路
为了实现这个功能我们可以使用Fisher-Yates洗牌算法来确保每个元素在每个位置的概率都是相等的。
三、具体代码
import java.util.Random;class Solution {private int[] original;private int[] shuffled;private Random rand;public Solution(int[] nums) {original nums.clone(); // 复制一份原始数组shuffled nums.clone(); // 初始化打乱数组rand new Random(); // 初始化随机数生成器}public int[] reset() {// 重置数组到初始状态return original.clone();}public int[] shuffle() {// 使用Fisher-Yates洗牌算法打乱数组for (int i shuffled.length - 1; i 0; i--) {int index rand.nextInt(i 1); // 生成一个[0, i]范围内的随机数// 交换当前元素与随机选中的元素int temp shuffled[index];shuffled[index] shuffled[i];shuffled[i] temp;}return shuffled;}
}/*** Your Solution object will be instantiated and called as such:* Solution obj new Solution(nums);* int[] param_1 obj.reset();* int[] param_2 obj.shuffle();*/在这个实现中我们维护了两个数组original用于存储初始状态shuffled用于存储打乱后的状态。reset方法返回original数组的副本而shuffle方法则使用Fisher-Yates算法打乱shuffled数组并返回打乱后的结果。
Fisher-Yates算法的工作原理是从数组的最后一个元素开始随机选择一个元素与之交换然后逐步向前处理直到处理到数组的第一个元素。这样每个元素都有相同的机会出现在数组的任何位置。
四、时间复杂度和空间复杂度
1. 时间复杂度 构造函数 Solution(int[] nums) nums.clone()这个操作的时间复杂度是 O(n)其中 n 是数组 nums 的长度。初始化 Random 对象这个操作的时间复杂度是 O(1)。 因此构造函数的总时间复杂度是 O(n)。 reset() 方法 original.clone()这个操作的时间复杂度是 O(n)因为需要复制整个原始数组。 因此reset() 方法的时间复杂度是 O(n)。 shuffle() 方法 Fisher-Yates 洗牌算法这个算法包含一个从后向前的循环循环体内有一个交换操作。循环的次数是 n-1其中 n 是数组的长度每次循环中的交换操作是 O(1)。 因此shuffle() 方法的时间复杂度是 O(n)。
2. 空间复杂度 构造函数 Solution(int[] nums) original 和 shuffled 数组每个数组都需要 O(n) 的空间来存储数组的副本。rand 对象这个对象的空间复杂度是 O(1)。 因此构造函数的总空间复杂度是 O(n)。 reset() 方法 返回的是 original 数组的副本但这个副本是在方法外部创建的所以方法本身不占用额外的空间。 因此reset() 方法的时间复杂度是 O(1)。 shuffle() 方法 方法内部只使用了常数额外空间用于交换元素时的临时变量 temp。 因此shuffle() 方法的时间复杂度是 O(1)。
3. 总结
时间复杂度构造函数和 shuffle() 方法都是 O(n)reset() 方法也是 O(n)。空间复杂度构造函数是 O(n)reset() 方法和 shuffle() 方法都是 O(1)。
五、总结知识点 类定义 class 关键字用于定义一个类。类名 Solution 是自定义的代表这个类的名称。 成员变量 private 关键字用于定义类的私有成员变量确保这些变量只能在类的内部访问。int[] original 和 int[] shuffled 分别用于存储原始数组和打乱后的数组。Random rand 是 java.util.Random 类的一个实例用于生成随机数。 构造函数 构造函数 Solution(int[] nums) 用于初始化类的实例。nums.clone() 方法用于创建原始数组的副本。 方法定义 public 关键字用于定义公共方法这些方法可以被类的外部访问。int[] reset() 和 int[] shuffle() 是两个公共方法分别用于重置数组和打乱数组。 数组操作 数组克隆使用 .clone() 方法复制数组。数组元素交换通过临时变量 int temp 来交换数组中的两个元素。 随机数生成 Random 类的实例 rand 用于生成随机数。rand.nextInt(i 1) 方法用于生成一个介于 [0, i] 范围内的随机整数。 Fisher-Yates洗牌算法 shuffle() 方法实现了Fisher-Yates洗牌算法这是一种高效的随机打乱数组的方法。算法从数组的最后一个元素开始随机选择一个元素与之交换然后逐步向前处理直到处理到数组的第一个元素。
以上就是解决这个问题的详细步骤希望能够为各位提供启发和帮助。
