Java-数据结构-随机数生成

一. 随机数生成方法

参考java的三种随机数生成方式 - cheng102e - 博客园 (cnblogs.com)

（1）new Random()

   Random r = new Random();

   r.nextInt(100);//生成0-100内的随机数

（2）Math.random()

       范围在 [0,1),如需要整型需要转成int使用

（3）currentTimeMillis()

long型，需要取余，也就是对随机数的范围取，比如（0-100），先%100，再转int

二. 随机数应用(leetcode实战) 

398. 随机数索引

给定一个可能含有重复元素的整数数组，要求随机输出给定的数字的索引。 您可以假设给定的数字一定存在于数组中。

class Solution {
    HashMap> map = new HashMap<>();
    public Solution(int[] nums) {   
        for(int i = 0; i < nums.length; i++){
            if(!map.containsKey(nums[i])){
                List list = new ArrayList<>();
                list.add(i);
                map.put(nums[i],list);
            }
            else{
                map.get(nums[i]).add(i);
            }
        }
    }
    
    public int pick(int target) {
       return map.get(target).get((int)(Math.random()*map.get(target).size()));
    }
}

三. 蓄水池采样

​​​​​​398. 随机数索引

 给定一个可能含有重复元素的整数数组，要求随机输出给定的数字的索引。 您可以假设给定的数字一定存在于数组中。

class Solution {
    private int[] nums;
    public Solution(int[] nums) {
       this.nums = nums;
    }
    
    public int pick(int target) {
        Random r = new Random();
        int n = 0;
        int index = 0;
        for(int i = 0;i < nums.length;i++)
            if(nums[i] == target){
            //我们的目标对象中选取。
                n++;
                //我们以1/n的概率留下该数据
                if(r.nextInt() % n == 0) index = i;
            }
        return index;
    }
}
作者：an-xin-9
链接：https://leetcode-cn.com/problems/random-pick-index/solution/xu-shui-chi-chou-yang-wen-ti-by-an-xin-9/