本文共 2131 字，大约阅读时间需要 7 分钟。

题目描述

给定一个可能含有重复元素的整数数组，要求随机输出给定的数字的索引。 您可以假设给定的数字一定存在于数组中。

注意：

题目示例

int[] nums = new int[] {
   1,2,3,3,3};Solution solution = new Solution(nums);// pick(3) 应该返回索引 2,3 或者 4。每个索引的返回概率应该相等。solution.pick(3);// pick(1) 应该返回 0。因为只有nums[0]等于1。solution.pick(1);

这题目中有一个地方需要注意，每一个索引返回的概率都是相同的。比较笨的方法就是将与 target 相等的元素存放到一个中间集合中，最后从中间集合随机取一个。第二种办法就是利用蓄水池抽样法来解决这个问题。

解法一：使用中间集合

我们先从头到尾遍历数组，将与 target 相等元素的索引，集中存储到中间集合 list 中，最后再从中间集合中随机返回一个元素索引。

1、解题代码：

class Solution {
       private int[] nums;    public Solution(int[] nums) {
           this.nums = nums;    }    public int pick(int target) {
           // 开辟一个中间集合        List
   
     list = new ArrayList<>();        for (int i = 0; i < nums.length; i++) {
               // 找出与target相等的元素            if (nums[i] == target) {
                   list.add(i);            }        }        // 如果只存在一个，就直接返回        if (list.size() == 1) return list.get(0);        // 如果有两个以上，随机取一个        return getRandomIndex(list);    }    /**     * 随机给出下标     *     * @param list 给定元素的索引集合     * @return     */    public int getRandomIndex(List
    
      list) {
           return list.get(new Random().nextInt(list.size()));    }}
    
   

复杂度分析

时间复杂度：需要遍历一次数组，所以时间复杂度是O(N)

空间复杂度：使用了 ArrayList ，ArrayList 的大小与数组有关，所以空间复杂度为O(N)

解法二：蓄水池抽样算法

这是我在 leetcode 上看到的解法，蓄水池抽样算法好像是一种专业的算法，关于算法的详情，大家就自行百度，我也不是太清楚，这里我就简单的描述：给定一个数据流，数据流长度N很大，且N直到处理完所有数据之前都不可知，请问如何在只遍历一遍数据（O(N)）的情况下，能够随机选取出m个不重复的数据。符合我们的题意，这里我就直接给出解题代码，具体的也不是很清楚，不过刷题不就是扩宽思维吗？

1、解题代码

class Solution {
       private int[] nums;    public Solution(int[] nums) {
           this.nums = nums;    }    public int pick(int target) {
           // 返回下标，没找到就返回-1        int index = -1;        // 记录查找到的个数        int count = 0;        for (int i = 0; i < nums.length; i++) {
               if (nums[i] == target) {
                   count++;                // 随机返回，new Random().nextInt() % count == 0 作为概率                if (new Random().nextInt() % count == 0) index = i;            }        }        return index;    }}

复杂度分析

时间复杂度：需要遍历一次数组，所以时间复杂度是O(N)

空间复杂度：没有使用新的集合，所以空间复杂度为O(1)

最后

欢迎扫码关注微信公众号：「平头哥的技术博文」，和平头哥一起学习，一起进步。

转载地址：https://blog.csdn.net/z694644032/article/details/103700178 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！