笔试记录(多益网络)从m个数中等概率取出n个数

从m个数中等概率取出n个数

题目要求从m个数中取出n个数，且保证每个数被取到的概率相等。

想到了这样一种解法，首先将m个数放入一个数组中，然后生成一个0到m-1的随机数，然后将这个随机数当做数组的下标去取对应的元素，我们将取到的这个元素加到结果集中。然后，将该数和数组中的最后一个数进行位置交换，然后生成下一个随机数，范围是0到m-2，取出对应下标的数加入结果集，然后将该数和数组的m-2位置的数互换，依此类推，直到取到第n个数。注意：每次取完当前数以后进行和最后一个数交换的原因是，这样可以在下一次取值中不会取到已经取出来的结果，保障了每一个元素被选中的概率相等，而且避免了删除算法带来的效率损耗。

java代码如下：

import java.util.ArrayList;
import java.util.List;

/**
 * 多益网络笔试题
 * @author 1
 *
 */
public class SelectRandom {
	public List<Integer> selectRandom(int [] arr,int n){
		List<Integer> list=new ArrayList<>();
		if(arr.length==0 || arr==null) {
			return list;
		}
		if(arr.length<=n) {
			for(int i:arr) {
				list.add(i);
			}
			return list;
		}
		
		for(int i=0;i<n;i++) {
			int rand=(int)(Math.random()*(arr.length-i-1)); //注意不要写成(int)Math.random()*(arr.length-i-1)，这个结果为0，因为先执行了强制转换
			list.add(arr[rand]);
			swap(arr,rand,arr.length-i-1);
		}
		return list;
	}
	public void swap(int [] arr, int i,int j) {
		int temp=arr[i];
		arr[i]=arr[j];
		arr[j]=temp;
	}
	public static void main(String[] args) {
		SelectRandom sr=new SelectRandom();
		int [] arr= {1,2,3,4,5,6,7};
		System.out.println(sr.selectRandom(arr,3));
	}
}