leetcode 398. Random Pick Index | 398. 随机数索引（Java）

忘是亡心i 2022-09-02 01:17 36阅读 0赞

## 题目 ##

[https://leetcode.com/problems/random-pick-index/][https_leetcode.com_problems_random-pick-index]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

常规思路，先用 map 存一串，取的时候从 map 对应的串中随机拿一个就 ok。

class Solution { 
        private Map<Integer, List<Integer>> map;
        private Random r;
    
        public Solution(int[] nums) { 
            r = new Random();
            map = new HashMap<>();
            for (int i = 0; i < nums.length; i++) { 
                if (!map.containsKey(nums[i])) { 
                    map.put(nums[i], new ArrayList<>());
                }
                map.get(nums[i]).add(i);
            }
        }
    
        public int pick(int target) { 
            int size = map.get(target).size();
            return map.get(target).get(r.nextInt(size));
        }
    }
    
    /** * Your Solution object will be instantiated and called as such: * Solution obj = new Solution(nums); * int param_1 = obj.pick(target); */

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

[https_leetcode.com_problems_random-pick-index]: https://leetcode.com/problems/random-pick-index/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/81abb3184a014052a7b5bfe75d46a41a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/0102912b26eb43b3a4331fc5254e43aa.png