随机取数使概率相等

缺乏、安全感 2024-04-08 11:28 64阅读 0赞

**题目**：随机地从大小为n个数中选取m个数。要求每个元素被选中的概率相等？

**分析**：这道题目和随机洗牌算法类似，只需要随机选取1个元素， 然后在剩下的元素里面随机选取下一个元素，不断这样操作即可。

这样做能保证每个元素选中的概率一样吗？也就是选中每个元素的概率都是1/n？ 答案是YES，让我们来做一下简单的计算。

选第1个元素：在n个中随机选，因此概率为1/n

选第2个元素：在剩下的n-1个中随机选：1/(n-1)，由于第1次没有选中它， 而是在另外n-1个中选：(n-1)/n，因此概率为：(n-1)/n \* 1/(n-1) = 1/n

选第3个元素：同上：(n-1)/n \* (n-2)/(n-1) \* 1/(n-2) = 1/n

。。。。。

**思路**：  
由于Random的nextInt(x) 方法是从 0 到 x-1 随机取数，所以使random的数视为从数组从后往前倒着数的索引；  
第一次 i=0 ，首先在索引0 到 n-1 共n个数之间取一个数，即 j= nextInt(n)，抽出来的数的索引是 n-1-j， 然后将这个下标对应的数和数组的i=0 处数交换位置；  
然后i=1时，从1到n-1共n-1个数之间用nextInt() 方法随机取一个数，nextInt()是从0到n-2取 所以是nextInt(n-1)，然后将下标对应的数和数组的第二个数交换位置。依次这样下去，知道找出m个数。

**注意**：  
Random对象的 nextInt(x) 方法，随机从0到x-1 之间取数，不包括 x ！

public class test02 {
        
        static List<Integer> r=new ArrayList<>();
        public static void main(String[] args) throws IOException {
        
            BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
            String s1 = in.readLine();
            String s2 = in.readLine();
            int n = Integer.parseInt(s1);
            int m = Integer.parseInt(s2);
            int[] nums = new int[n];
            for (int i = 0; i < n; i++) {
        
                nums[i] = i;
            }
            select(nums, m);
            for(int k:r){
        
                System.out.println(k);
            }
    
        }
    
        static void select(int[] nums, int m) {
        
            int n=nums.length;
            for (int i = 0; i < m; i++) {
        
                // Random.nextInt(x) 随机筛选0到x-1之间的数 ！
                // 每次筛选以i为起点，所以实际筛出来的数的索引是  n-1-筛的索引
                int randomindex=n-1-new Random().nextInt(n-i);
                r.add(nums[randomindex]);
                //交换
                int temp=nums[i];
                nums[i]=nums[randomindex];
                nums[randomindex]=temp;
            }
        }
    }

参考：https://blog.csdn.net/m0\_46450708/article/details/121067627