[数据结构与算法]398. 随机数索引（哈希表预处理 Or 蓄水池抽样）

Question

398. 随机数索引

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

Ideas

1、Answer( Java )

解法思路：哈希表预处理

?? getOrDefault(Object key, V defaultValue)

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

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

Code①（ HashMap 实现）

/**
 * @author Listen 1024
 * @description 398. 随机数索引（哈希表预处理 Or 蓄水池抽样）
 * @date 2022-04-25 10:50
 */
class Solution {
    Random random = new Random();
    Map<Integer, List<Integer>> map = new HashMap<>();

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

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


/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int param_1 = obj.pick(target);
 */

Code②（ ArrayList 实现）

/**
 * @author Listen 1024
 * @description 398. 随机数索引（哈希表预处理 Or 蓄水池抽样）
 * @date 2022-04-25 10:50
 */
 class Solution {
    ArrayList<Integer> list = new ArrayList<>();

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

    public int pick(int target) {
        int res = 0;
        ArrayList<Integer> 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;
    }

}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int param_1 = obj.pick(target);
 */

2、Answer( Java )

解法思路：蓄水池抽样

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

Code（ 蓄水池抽样 ）

/**
 * @author Listen 1024
 * @description 398. 随机数索引（哈希表预处理 Or 蓄水池抽样）
 * @date 2022-04-25 10:50
 */
 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;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int param_1 = obj.pick(target);
 */

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

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖