🌕🌗 398. 随机数索引

难度: 🌕🌗

问题描述

---

解法 1 - Hash

class Solution {
    // 思路：
    // 在初始化时，将所有元素 和出现次数记录在 map 中
    // 时间复杂度 O(N) & O(1) 空间复杂度 O(N)
    HashMap<Integer, ArrayList<Integer>> map;
    Random rand;

    public Solution(int[] nums) {
        rand = new Random();
        map = new HashMap<>();
        // 复杂度 O(N)
        int len = nums.length;
        for(int i = 0; i < len; i ++) {
            int cur = nums[i];
            if(!map.containsKey(cur)) {
                ArrayList<Integer> tmp = new ArrayList<>();
                map.put(cur, tmp);
            } 
            ArrayList<Integer> list = map.get(cur);
            list.add(i);
            map.put(cur, list);
        }
    }
    
    public int pick(int target) {
        if(!map.containsKey(target)) {
            return -1;
        }
        // 复杂度 O(1)
        ArrayList<Integer> list = map.get(target);
        int size = list.size();
        int index = rand.nextInt(size);
        return list.get(index);
    }
}

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

---

输出 1

---

解法 2 - 蓄水池

class Solution {
    // 思路：
    // 常规思路是在初始化时保存所有元素和出现次数
    // 若大数据背景下，内存放不下文件系统中的所有元素，此时使用 map 存储超内存
    // 采用蓄水池算法
    // 在初始化时不做处理，在挑选随机数时，遍历 O(N) 但不存储所有元素，只有单个变量，此时空间复杂度就降低了
    // 时间复杂度 O(1) & O(N) 空间复杂度 O(1)
    Random rand;
    int[] nums;

    public Solution(int[] nums) {
        // 复杂度 O(1)
        rand = new Random();
        this.nums = nums;
    }
    
    public int pick(int target) {
        // 复杂度 O(N)
        int len = nums.length;
        int count = 0; // target 的出现次数
        int res = 0;
        for(int i = 0; i < len; i ++) {
            int cur = nums[i];
            if(cur == target) {
                // 只有目标出现时，才进行操作
                count ++;
                int index = rand.nextInt(count); // [0, count - 1] 中抽样，假设抽到 0 就进行替换
                if(index == 0) {
                    res = 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