LeetCode 398. 随机数索引

Categories:

题目描述
思路分析
1. 解法一：蓄水池抽样（推荐）
相似题目

题目描述

✅ 398. 随机数索引

思路分析

解法一：蓄水池抽样（推荐）

核心思路：

遍历数组，遇到目标值时计数 count 加一。

以 1 / count 的概率选择当前索引作为答案。

保证所有目标索引被选中的概率相同。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(1)，仅使用常数额外空间。

import java.util.Random;

class Solution {
    private final int[] nums;
    private final Random random = new Random();

    public Solution(int[] nums) {
        this.nums = nums;
    }

    public int pick(int target) {
        int count = 0;
        int res = -1;

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                count++;

                // 以 1 / count 的概率替换答案
                if (random.nextInt(count) == 0) {
                    res = i;
                }
            }
        }

        return res;
    }
}

import "math/rand"

type Solution struct {
	nums []int
}

func Constructor(nums []int) Solution {
	return Solution{nums: nums}
}

func (s *Solution) Pick(target int) int {
	count := 0
	res := -1

	for i, v := range s.nums {
		if v == target {
			count++

			// 以 1 / count 的概率替换答案
			if rand.Intn(count) == 0 {
				res = i
			}
		}
	}

	return res
}

相似题目

题目	难度	考察点
382. 链表随机节点	中等	蓄水池抽样
384. 打乱数组	中等	随机
528. 按权重随机选择	中等	随机
470. 用 Rand7() 实现 Rand10()	中等	随机
519. 随机翻转矩阵	中等	随机

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/66348730