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

阳光穿透心脏的1/2处 2022-08-05 01:20 168阅读 0赞

http://blog.csdn.net/caishenfans/article/details/6743512

从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后面的数字

**\[java\]** [view plain][] [copy][view plain] [print][view plain] [?][view plain]

1.  **import** java.util.Random; 
2.  
3.  
4.  
5.  **public****class** Rand \{ 
6.  
7.  **public****static****void** randSelect(**int**\[\] nums, **int** n) \{ 
8.   Random rand = **new** Random(); 
9.  **for**(**int** i = 0; i < n; i ++)\{ 
10.  swap(nums , i, rand.nextInt(nums.length-i)+i); 
11.  \} 
12.  \} 
13. 
14. **public****static****void** swap(**int**\[\] nums, **int** m , **int** n)\{ 
15. **int** temp = nums\[n\]; 
16.  nums\[n\] = nums\[m\]; 
17.  nums\[m\] = temp; 
18.  \} 
19. 
20. **public****static****void** main(String\[\] args) \{ 
21. **int**\[\] nums = **new****int**\[100\]; 
22. **for**(**int** i = 0;i < 100;i++)\{ 
23.  nums\[i\]=i; 
24.  \} 
25.  randSelect(nums,10); 
26. **for**(**int** i = 0;i < 10; i ++)\{ 
27.  System.out.println(nums\[i\]); 
28.  \} 
29.  \} 
30. \} 
31. 
32. /\*output : 
33. 27
34. 79
35. 30
36. 58
37. 41
38. 54
39. 75
40. 18
41. 26
42. 5
43. \*/

这是等概率的么？ 答案是肯定的

[view plain]: http://blog.csdn.net/caishenfans/article/details/6743512#