基本信息

  • 题号：384
  • 题厂：谷歌
  • 难度系数：中


已知一个数组，设计两个方法：

  1. 将数组元素洗牌，每个元素都有相同洗牌几率。
  2. 将数组重新归回为初始状态。
["Solution", "shuffle", "reset", "shuffle"]
[[[1, 2, 3]], [], [], []]
返回 [null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]
“Solution” 表示初始化了一个 [1, 2, 3] 的数组


解题思路

  • 「初始化」：既然要设计两个方法，一个洗牌一个还原——可以在初始化对象时创建两个数组：一个洗牌数组，一个初始数组；
  • 「还原」：当调用还原方法时，我们把洗牌数组的值还原到初始数组；
  • 「洗牌」：随机洗牌多半需要调用 random，此处需要设计如何具体洗牌。。。


import random

class Solution:
    # 初始化数组时，需要使用深度拷贝，以免数组串位。
    def __init__(self, nums: List[int]):
        self.array = nums
        self.original = nums.copy()

    # 同样重置数组时，也需要使用深度拷贝。
    def reset(self) -> List[int]:
        self.array = self.original
        self.original = self.original.copy()
        return self.array
    
    # 洗牌时，我们通过 for 循环遍历，每个元素和它后面的元素随机置换。。。
    def shuffle(self) -> List[int]:
        for i in range(len(self.array)):
            swap_idx = random.randrange(i, len(self.array))
            self.array[i], self.array[swap_idx] = self.array[swap_idx], self.array[i]
        return self.array


Constraints

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


Big O

  • 时间复杂度：O（n）
  • 空间复杂度：O（n）



Java 版

Object 设计题推荐 Java。

对比之后发现，实现同样的功效，Java 需要比 Python 多写很多行代码……

import java.util.Random;

class Solution {

    private int[] original;
    private int[] array;
    Random rand = new Random();

    public Solution(int[] nums) {
        array = nums;
        original = nums.clone();
    }
    
    public int[] reset() {
        array = original;
        original = original.clone();
        return array;
    }

    private int randRange(int min, int max) {
        return rand.nextInt(max -  min) + min;
    }
    
    public int[] shuffle() {
        for (int i = 0; i < array.length; i ++ ) {
            int swapIdx = randRange(i, array.length);
            int temp = array[i];
            array[i] = array[swapIdx];
            array[swapIdx] = temp;
        }
        return array;
    }
}


总结

  • 除了洗牌算法外，本题还考察了有实际通途的「数组深度拷贝」。
original = nums.clone();

original = nums;


  • 作为一道有实际考点，考点略不常规的题，需要重点复习，不留死角！！！