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

注意：
数组大小可能非常大。 使用太多额外空间的解决方案将不会通过测试。

示例:

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);

  1. class Solution {
  2.     Map<Integer, List<Integer>> map = new HashMap<>();
  3.     Random random = new Random();
  4.     public Solution(int[] nums) {
  5.         int n = nums.length;
  6.         for (int i = 0; i < n; ++i) {
  7.             List<Integer> list = map.getOrDefault(nums[i], new ArrayList<>());
  8.             list.add(i);
  9.             map.put(nums[i], list);
  10.         }
  11.     }
  13.     public int pick(int target) {
  14.         List<Integer> list = map.get(target);
  15.         return list.get(random.nextInt(list.size()));
  16.     }
  17. }
  19. /**
  20.  * Your Solution object will be instantiated and called as such:
  21.  * Solution obj = new Solution(nums);
  22.  * int param_1 = obj.pick(target);
  23.  */

蓄水池抽样

image.png

  1. class Solution {
  2.     //蓄水池抽样
  3.     int[] nums;
  4.     Random random = new Random();
  5.     public Solution(int[] nums) {
  6.         this.nums = nums;
  7.     }
  9.     public int pick(int target) {
  10.         int n = nums.length;
  11.         int res = 0;
  12.         for (int i = 0, cnt = 0; i < n; ++i) {
  13.             if (nums[i] == target) {
  14.                 cnt ++;
  15.                 if (random.nextInt(cnt) == 0) res = i;
  16.             }
  17.         }
  18.         return res;
  19.     }
  20. }
  22. /**
  23.  * Your Solution object will be instantiated and called as such:
  24.  * Solution obj = new Solution(nums);
  25.  * int param_1 = obj.pick(target);
  26.  */