LeetCode 384. 打乱数组

384. 打乱数组

题目：给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。打乱后，数组的所有排列应该是 等可能 的。
实现 Solution class:
Solution(int[] nums) 使用整数数组 nums 初始化对象
int[] reset() 重设数组到它的初始状态并返回
int[] shuffle() 返回数组随机打乱后的结果

链接 https://leetcode.cn/problems/shuffle-an-array/

官方思路

1. 暴力
   
   

class Solution:
    def __init__(self, nums: List[int]):
        self.nums = nums
        self.original = nums.copy()

    def reset(self) -> List[int]:
        self.nums = self.original.copy()
        return self.nums

    def shuffle(self) -> List[int]:
        shuffled = [0] * len(self.nums)
        for i in range(len(self.nums)):
            j = random.randrange(len(self.nums))
            shuffled[i] = self.nums.pop(j)
        self.nums = shuffled
        return self.nums

# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.reset()
# param_2 = obj.shuffle()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2. 洗牌算法
（1）考虑通过调整 }waiting 的实现方式以优化方法一。
（2）我们可以在移除 waiting 的第 k 个元素时，将第 k 个元素与数组的最后 1 个元素交换，然后移除交换后数组的最后 1 个元素，这样我们只需要 O(1) 的时间复杂度即可完成移除第 k 个元素的操作。此时，被移除的交换后数组的最后 1 个元素即为我们根据随机下标获取的元素。
（3）在此基础上，我们也可以不移除最后 1 个元素，而直接将其作为乱序后的结果，并更新待乱序数组的长度，从而实现数组的原地乱序。因为我们不再需要从数组中移除元素，所以也可以将第 k 个元素与第 1 个元素交换。

class Solution:
    def __init__(self, nums: List[int]):
        self.nums = nums
        self.original = nums.copy()

    def reset(self) -> List[int]:
        self.nums = self.original.copy()
        return self.nums

    def shuffle(self) -> List[int]:
        for i in range(len(self.nums)):
            j = random.randrange(i, len(self.nums))
            self.nums[i], self.nums[j] = self.nums[j], self.nums[i]
        return self.nums
1
2
3
4
5
6
7
8
9
10
11
12
13
14

复杂度分析
时间复杂度：
初始化：O(n)，其中 n 为数组中的元素数量。我们需要 O(n) 来初始化 original。
reset：O(n)。我们需要 O(n) 将 original 复制到 nums。
shuffle：O(n)。我们只需要遍历 n 个元素即可打乱数组。
空间复杂度：O(n)。记录初始状态需要存储 n 个元素。

其他思路

1. 等通知：直接random

class Solution:

    def __init__(self, nums: List[int]):
        self.arr1 = nums

    def reset(self) -> List[int]:
        return self.arr1

    def shuffle(self) -> List[int]:
        shuffArr = self.arr1.copy()
        random.shuffle(shuffArr)
        return shuffArr
1
2
3
4
5
6
7
8
9
10
11
12

参考：
作者：LeetCode-Solution
链接：https://leetcode.cn/problems/shuffle-an-array/solution/da-luan-shu-zu-by-leetcode-solution-og5u/