力扣-398. 随机数索引

朴灿烈づ我的快乐病毒、 2022-10-11 01:23 82阅读 0赞

> 给定一个可能含有重复元素的整数数组，要求随机输出给定的数字的索引。 您可以假设给定的数字一定存在于数组中。
> 
> 注意：  
> 数组大小可能非常大。 使用太多额外空间的解决方案将不会通过测试。
> 
> 示例:
> 
> int\[\] nums = new int\[\] \{1,2,3,3,3\};  
> Solution solution = new Solution(nums);
> 
> // pick(3) 应该返回索引 2,3 或者 4。每个索引的返回概率应该相等。  
> solution.pick(3);
> 
> // pick(1) 应该返回 0。因为只有nums\[0\]等于1。  
> solution.pick(1);

## 我的解法 ##

我的思路：从题中获取到的信息是，数组中元素可能重复。但是想要获取的数据一定会出现在数组中。 问题是：没有说数组中的元素是否有序。

我第一时间想到的是：使用 HashMap<Integer, ArrayList<Integer>> 这个结构来存储，全部的数据，ArrayList里边放的是重复的元素的 下标。采用这样的结构存储，可以做到时间复杂度为：O（n），实际上就是遍历一遍数组的问题。然后在pick（）方法中，我可以直接获取到该元素的所有下标，然后我唯一要解决的是，如何保证等概率的从这个数组中获取下标的问题。 我想要的是使用 Random的 netInt（数组的长度）的方法，来获取到下标。

class Solution {
    
    	HashMap<Integer, ArrayList<Integer>> relation = null;
    	public Solution(int[] nums) {
    
    		relation = new HashMap<>(nums.length);
    		for (int i = 0; i < nums.length; i++) {
    			if(relation.containsKey(nums[i])){
    				relation.get(nums[i]).add(i);
    			}else {
    				Integer temp = i;
    				ArrayList list = new ArrayList();
    				list.add(Integer.valueOf(i));
    				relation.put(nums[i], list);
    			}
    		}
    	}
    
    	public int pick(int target) {
    		ArrayList resultList = relation.get(target);
            Random random = new Random();
    		return (int) resultList.get(random.nextInt(resultList.size()));
    	}
    }
    
    /**
     * Your Solution object will be instantiated and called as such:
     * Solution obj = new Solution(nums);
     * int param_1 = obj.pick(target);
     */

## 别人的解法:(力扣) ##

实际上也是遍历一遍。相比较我的，时间复杂度一样。空间复杂度比我的小。 但是这是建立在调用一次 pick的方法上，如果想要获取全部元素，那么时间复杂度就是 O(n\*n)了。

蓄水池采样算法  
保留概率 = i本次被选择的概率 \* 其他都未被选中的概率

class Solution {
        int[] nums;
        public Solution(int[] nums) {
            this.nums = nums;
        }
    
        // 蓄水池采样算法
        // 保留概率 = i本次被选择的概率 * 其他都未被选中的概率
        
        // 本次选中 1  1/2  1/3  1/4    (出现4次)
        // 未被选中 0  1/2  2/3  3/4    
        // 保留概率    1/4  1/4  1/4
        // k/(k+1) 连乘之后结果为k/n  
    
        public int pick(int target) {
            Random r = new Random();
            int count = 0, ret = 0;
            for (int i = 0; i < nums.length; ++i) {
                if (nums[i] == target) {
                    if (r.nextInt(++count) == 0) {
                        ret = i;
                    }
                }
            }
            return ret;
        }
    }

## 这道题给我带来的收货 ##

延伸：如何获取到 0 - 10 中的一个随机整数？

我们可以借助 Random的 nextInt 方法

Random random = new Random();
     random.nextInt(10);