384.打乱数组.md

384.打乱数组

/*
 * @lc app=leetcode.cn id=384 lang=typescript
 *
 * [384] 打乱数组
 */

// @lc code=start
class Solution {
  constructor(nums: number[]) {}

  reset(): number[] {}

  shuffle(): number[] {}
}

/**
 * Your Solution object will be instantiated and called as such:
 * var obj = new Solution(nums)
 * var param_1 = obj.reset()
 * var param_2 = obj.shuffle()
 */
// @lc code=end

解法 1: Fisher-Yates 洗牌算法

• 时间复杂度:
• 空间复杂度:

只适合已知长度的数组,对于第 i 个位置,随机选取 i~n-1 范围内的一个数跟 i 进行交换

class Solution {
  _nums: number[]
  constructor(nums: number[]) {
    this._nums = [...nums]
  }

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

  shuffle(): number[] {
    const n = this._nums.length
    const nums = [...this._nums]
    for (let i = 0; i < n; i++) {
      const num = Math.floor(Math.random() * (n - i)) + i
      ;[nums[i], nums[num]] = [nums[num], nums[i]]
    }
    return nums
  }
}

解法 2: Inside-Out Algorithm 算法

可以用于未知长度的数组,选取第 i 个数时,从 0~i 中随机选取一个数跟第 i 个数进行交换

class Solution {
  _nums: number[]
  constructor(nums: number[]) {
    this._nums = [...nums]
  }

  reset(): number[] {
    return this._nums
  }
  shuffle(): number[] {
    const res: number[] = []
    for (let i = 0; i < this._nums.length; i++) {
      res.push(this._nums[i])
      const j = Math.floor(Math.random() * (i + 1))
      ;[res[i], res[j]] = [res[j], res[i]]
    }
    return res
  }
}