leetcode每日一题 398. 随机数索引

class Solution {
?
    private int[] nums;
?
    public Solution(int[] nums) {
        this.nums = nums;
    }
    
    public int pick(int target) {
        List list = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] == target){
                list.add(i);
            }
        }
        Collections.shuffle(list);
        return list.get(0);
    }
}

用hashmap 先初始化数据，然后取值直接拿结果性能并没有提高，只有查询操作特别大的时候，性能较高，此题显然不适合

class Solution {
?
    private Map> map = new HashMap<>();
?
    public Solution(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if(map.containsKey(nums[i])){
                map.get(nums[i]).add(i);
            }else {
                List list = new ArrayList<>();
                list.add(i);
                map.put(nums[i],list);
            }
        }
    }
    
    public int pick(int target) {
        List list = map.get(target);
        Collections.shuffle(list);
        return list.get(0);
    }
}