1. 题目

https://leetcode-cn.com/problems/random-pick-index/
给定一个可能含有重复元素的整数数组，要求随机输出给定的数字的索引。 您可以假设给定的数字一定存在于数组中。
注意：
数组大小可能非常大。 使用太多额外空间的解决方案将不会通过测试。
示例:

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

2. 题解

2022-04-25 AC, 定长的就比较简单, 直接map, 如果实际中是流的数据方式更推荐”蓄水池抽样”解法

  1. <?php
  2.   /**
  3.   * Created by PhpStorm
  4.   * User: jtahstu
  5.   * Time: 2022/4/25 10:05
  6.   * Des: 398. 随机数索引
  7.   *      https://leetcode-cn.com/problems/random-pick-index/
  8.   *      给定一个可能含有重复元素的整数数组，要求随机输出给定的数字的索引。 您可以假设给定的数字一定存在于数组中。
  9.   * 注意：数组大小可能非常大。 使用太多额外空间的解决方案将不会通过测试。
  10.   */
  12.   class Solution
  13. {
  14.   private $list;
  16.   /**
  17.   * @param Integer[] $nums
  18.   */
  19.   function __construct($nums)
  20.   {
  21.     foreach ($nums as $k => $num) {
  22.       $this->list[$num][] = $k;
  23.     }
  24.   }
  26.   /**
  27.   * @param Integer $target
  28.   * @return Integer
  29.   */
  30.   function pick($target)
  31.   {
  32.     $indexs = $this->list[$target];
  33.     return $indexs[rand(0, count($indexs) - 1)];
  34.   }
  35. }
  37. /**
  38. * Your Solution object will be instantiated and called as such:
  39. * $obj = Solution($nums);
  40. * $ret_1 = $obj->pick($target);
  41. */
  43. $solution = new Solution([1, 2, 3, 3, 3]);
  44. var_dump($solution->pick(3));
  45. var_dump($solution->pick(1));
  47. /**
  48. * 执行用时：116 ms, 在所有 PHP 提交中击败了100.00%的用户
  49. * 内存消耗：39.1 MB, 在所有 PHP 提交中击败了50.00%的用户
  50. * 通过测试用例：14 / 14
  51.  */
  1. 咱这属于哈希表预处理（定长数据流）
    2. 另一个解法是蓄水池抽样（不定长数据流）
    关于该解法为啥选取的概率相同, 可谷歌证明方式 ```java class Solution { Random random = new Random(); int[] nums; public Solution(int[] _nums) {
     nums = _nums;
    } public int pick(int target) {
     int n = nums.length, ans = 0;
 for (int i = 0, cnt = 0; i < n; i++) {
     if (nums[i] == target) {
         cnt++;
         if (random.nextInt(cnt) == 0) ans = i;
     }
 }
 return ans;
    }

```