当前位置：首页 > article >正文

LeetCode题练习与总结：打乱数组--384

article 2024/11/13 3:51:58

一、题目描述

给你一个整数数组 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

二、解题思路

为了实现这个功能，我们可以使用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洗牌算法，这是一种高效的随机打乱数组的方法。
- 算法从数组的最后一个元素开始，随机选择一个元素与之交换，然后逐步向前处理，直到处理到数组的第一个元素。