398.随机数索引.md

398.随机数索引

/*
 * @lc app=leetcode.cn id=398 lang=typescript
 *
 * [398] 随机数索引
 */

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

  pick(target: number): number {}
}
/**
 * Your Solution object will be instantiated and called as such:
 * var obj = new Solution(nums)
 * var param_1 = obj.pick(target)
 */
// @lc code=end

解法 1: 哈希表

class Solution {
  private map = new Map<number, number[]>()
  constructor(nums: number[]) {
    for (let [i, num] of nums.entries()) {
      if (!this.map.has(num)) this.map.set(num, [])
      this.map.get(num)!.push(i)
    }
  }

  pick(target: number): number {
    const indexs = this.map.get(target)
    const i = Math.floor(Math.random() * indexs.length)
    return indexs[i]
  }
}