398. 随机数索引（哈希表预处理 Or 蓄水池抽样）

• Question
• Ideas
• • 1、Answer( Java )
  • • • `⚡️ getOrDefault(Object key, V defaultValue)`
    • Code①（ HashMap 实现）
    • Code②（ ArrayList 实现）
  • 2、Answer( Java )
  • • Code（ 蓄水池抽样 ）

398. 随机数索引

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/random-pick-index/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法思路：哈希表预处理

获取指定 key 对应对 value，如果找不到 key ，则返回设置的默认值。

使用哈希表以 nums[i] 为键，下标集合 List 作为值进行存储。（ ArrayList 同理）

class Solution {
    Random random = new Random();
    Map> map = new HashMap<>();

    public Solution(int[] nums) {
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            List list = map.getOrDefault(nums[i], new ArrayList());
            list.add(i);
            map.put(nums[i], list);
        }
    }

    public int pick(int target) {
        int res = 0;
        List list = map.get(target);
        int i = random.nextInt(list.size());
        res = list.get(i);
        return res;
    }
}

 class Solution {
    ArrayList list = new ArrayList<>();

    public Solution(int[] nums) {
        for (int num : nums) {
            list.add(num);
        }
    }

    public int pick(int target) {
        int res = 0;
        ArrayList cnt = new ArrayList<>();
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i) == target) {
                cnt.add(i);
            }
        }
        Random random = new Random();
        int i = random.nextInt(cnt.size());
        res = cnt.get(i);
        return res;
    }

}

解法思路：蓄水池抽样

规定当遇到第 k 个满足 nums[i]=target 的下标时，执行一次 [0, k) 的随机操作，当随机结果为 0 时（ 发生概率为 1/k )，我们将该坐标作为最新的答案候选。

 class Solution {
    Random random = new Random();
    int[] _nums;

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

    public int pick(int target) {
        int index = 0, cnt = 0;
        int len = _nums.length;
        for (int i = 0; i < len; i++) {
            if (_nums[i] == target) {
                cnt++;
                if (random.nextInt(cnt) == 0) {
                    index = i;
                }
            }

        }
        return index;
    }
}

题解二参考链接
https://leetcode-cn.com/problems/random-pick-index/solution/by-ac_oier-zhml/