从M个数中随机等可能的取出N个的问题

从0到m-1这m个数中随机取出n个（n<=m）要求每个数被取到的可能性相等。
第一个方法是把这m个数丢到一个List里面然后用nextInt(list.size())来产生随机数然后把list里面对应的元素丢到另一个数组或者list里面这个方法本来是不错的但要注意的是为了保证每个元素取到的概率相等需要每取出一个元素就把它从list里面删除原因就不解释了简单的概率问题。但众所周知的是 list的remove（int index）方法效率并不高尤其是当m和n很大的时候每一次调用remove ArrayList都需要进行数组的copy 而LinkedList需要进行链表的遍历。
所以再考虑这个问题，用数组来储存这m个数是很好的而且其实我们并不需要知道到底哪些下标的元素被选中了第一个方法的效率低下的原因在于 nextInt(int i)这个方法是从0 到i-1随机生成整数这里要求0到i-1是连续的i个整数而我们选取了一个数之后为了满足连续整数的条件就要把这个数删去而频繁删除的效率是低下的所以换一种思路不采用删除而采用交换

第二个方法比如0-99这100个数字从小到大放在一个数组里面现在要选10个我们只需要随机打乱这个数组然后选取前10个元素就好随机打乱的方法就是从数组头元素开始每次产生一个随机数n 然后交换这两个数而且只需要交换十次就够了因为我们并不取下标超过10后面的数字

import java.util.Random;  

public class Rand {  

    public static void randSelect(int[] nums, int n) {

        Random rand = new Random();

        for(int i = 0; i < n; i ++){

            swap(nums , i, rand.nextInt(nums.length-i)+i);

        }

    }  

    public static void swap(int[] nums, int m , int n){

        int temp = nums[n];

        nums[n] = nums[m];

        nums[m] = temp;

    }  

    public static void main(String[] args) {

        int[] nums = new int[100];

        for(int i = 0;i < 100;i++){

            nums[i]=i;

        }

        randSelect(nums,10);

        for(int i = 0;i < 10; i ++){

            System.out.println(nums[i]);

        }

    }

}  

/*output :&nbsp;

27

79

30

58

41

54

75

18

26

5

*/

巴特西

从M个数中随机等可能的取出N个的问题

最新文章

热门文章