水塘抽样随机取 1 个元素，哈希表，2 解法求解《398. 随机数索引》
水塘抽样
选 1 个元素，证明如上图
从 [0, n) 选 目标元素，统计目标元素出现次数 j
- 若
rand[0, j) == 0选中
代码模板 · 水塘抽样
选 1 个元素
function reservoirSampling = target => {
const n = nums.length
let j = ans = 0
for (let i = 0; i < n; i++) {
if (nums[i] === target) {
j++
if (Math.random() * j | 0 === 0) ans = i
}
}
return ans
}例题
398. 随机数索引
给定一个可能含有重复元素的整数数组，要求随机输出给定的数字的索引。 您可以假设给定的数字一定存在于数组中。 注意： 数组大小可能非常大。 使用太多额外空间的解决方案将不会通过测试。
答案
哈希表 · 哈希映射
var Solution = function(nums) {
this.h = new Map
for (let i = 0; i < nums.length; i++) {
if (!this.h.has(nums[i])) this.h.set(nums[i], [i])
else this.h.get(nums[i]).push(i)
}
};
Solution.prototype.pick = function(target) {
const nums = this.h.get(target)
return nums[Math.random() * nums.length | 0]
}; type Solution struct {
h map[int][]int
}
func Constructor(nums []int) Solution {
h := map[int][]int{}
for i, v := range nums {
h[v] = append(h[v], i)
}
return Solution{h:h}
}
func (this *Solution) Pick(target int) int {
indices := this.h[target]
return indices[rand.Intn(len(indices))]
}class Solution {
protected $h;
function __construct($nums) {
foreach ($nums as $i => $v) {
$this->h[$v] []= $i;
}
}
function pick($target) {
shuffle($this->h[$target]);
return $this->h[$target][0];
}
}水塘抽样
var Solution = function(nums) {
this.nums = nums
};
Solution.prototype.pick = function(target) {
const n = this.nums.length
let ans = 0
for (let i = 0, j = 0; i < n; i++) {
if (this.nums[i] === target) {
j++
if ((Math.random() * j | 0) === 0) {
ans = i
}
}
}
return ans
}; type Solution struct {
nums []int
}
func Constructor(nums []int) Solution {
return Solution{nums:nums}
}
func (this *Solution) Pick(target int) int {
j, ans := 0, 0
for i, v := range this.nums {
if v == target {
j++
if rand.Intn(j) == 0 {
ans = i
}
}
}
return ans
}class Solution {
protected $nums;
function __construct($nums) {
$this->nums = $nums;
}
function pick($target) {
$j = 0;
$ans = 0;
foreach($this->nums as $i => $v) {
if ($v === $target) {
$j++;
if (rand(0, $j - 1) === 0) {
$ans = $i;
}
}
}
return $ans;
}
}