打乱数组

发表于 | 分类于 |
字数统计: 603 字 | 阅读时长 ≈ 2 分钟

题目描述：给你一个整数数组 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]

洗牌

  • 还原：保存原数组的备份
  • 打乱：循环遍历nums，获取区间[i,len-1]范围内的随机整数j，交换i和j对应的位置
    • 举例来说：数组的长度为10，那我生成0到10的范围内的随机数，然后跟索引0的元素交换，这样数组索引0的已经打乱了
    • 依此类推：生成1到9范围内的随机数，然后跟索引1的元素交换，这样数组索引1的就已经打乱了
    • 重复上述这一个操作即可打乱整个数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var Solution = function (nums) {
  this.nums = nums;
  // 保存原数组的备份  在reset还原的时候可直接拿来用
  this.original = this.nums.slice();
};

Solution.prototype.reset = function () {
  // 从备份中还原
  this.nums = this.original.slice();
  return this.nums;
};

Solution.prototype.shuffle = function () {
  for (let i = 0; i < this.nums.length; ++i) {
    // 现在假设数组长度为10
    //  举例来说i是0的时候，生成0-10之间的随机数，i是1的话，生成1到9之间的随机数，依此类似
    const j = Math.floor(Math.random() * (this.nums.length - i)) + i;
    [this.nums[i], this.nums[j]] = [this.nums[j], this.nums[i]];
  }
  return this.nums;
};

复杂度分析

  • 时间复杂度：

    • 初始化：O(n)，其中 n 为数组中的元素数量。我们需要 O(n) 来初始化 original
    • reset：O(n)。我们需要 O(n) 将 original 复制到 nums
    • shuffle：O(n)。我们只需要遍历 n 个元素即可打乱数组

  • 空间复杂度：O(n)。记录初始状态需要存储 n 个元素