zhangdizhangdi

384. 打乱数组 🟨

题目

leetcode 中等

题目

给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。打乱后，数组的所有排列应该是 等可能 的。

实现 Solution class:

  • Solution(int[] nums) 使用整数数组 nums 初始化对象
  • int[] reset() 重设数组到它的初始状态并返回
  • int[] shuffle() 返回数组随机打乱后的结果

示例：
输入
[“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]

题解

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

    记录初始状态需要存储 n 个元素。

js
var Solution = function (nums) {
  this.nums = nums
  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) {
    const j = Math.floor(Math.random() * (this.nums.length - i)) + i
    ;[this.nums[j], this.nums[i]] = [this.nums[i], this.nums[j]]
  }
  return this.nums
}

const solution = new Solution([1, 2, 3])
console.log(solution.shuffle())
console.log(solution.reset())
console.log(solution.shuffle())
执行结果
[ 1, 2, 3 ]
[ 1, 2, 3 ]
[ 2, 1, 3 ]
ts
class Solution {
  nums: Array<number>;

  constructor(nums: number[]) {
    this.nums = nums;
  }

  reset(): number[] {
    return this.nums;
  }

  shuffle(): number[] {
    let arr = [...this.nums];
    let n = arr.length;
    for (let i = 0; i < n; i++) {
      // 从 i 到 n-1 随机选一个
      const rand = randOne(i, n - 1);
      // 交换nums数组i和rand下标的两个元素
      [arr[i], arr[rand]] = [arr[rand], arr[i]];
    }
    return arr;
  }
}

// 获取闭区间 [n, m] 内的一个随机整数
function randOne(n, m) {
  return Math.floor(Math.random() * (m - n + 1)) + n;
}