本文共 906 字，大约阅读时间需要 3 分钟。

这个问题本身不难理解，但是关键的地方是理解等概率，还有一个隐性的条件，那就是不能重复取。

所以初步的想法是用Rand()在[0,N]范围内生成M个随机数字，万一里面有重复数字，那这就不好玩了。

为了避免重复数字，那咱就给他生成随机的偏移量呗，假如我们当前取到的数字是a[i]，生成一个随机数字r，那么我们下一个取得数字就是a[i+r]。

可是这种做法也有点小问题，假如还没取完，然后数据就越界了，咋办？你可能会说：对整个N求个余呗，不是又回到前面了嘛！好，想法不错，可是等概率这个游戏规则又违反了，而且还是很可能取到重复的数字，啥意思呢，要是你生成的数字比较小，下标加和没有越界，那前面没取到的数字就跟这趟没关系了，这样会导致前面的宝宝不爽。

好了啰嗦了这么多，到底怎么解决，下面就是解决方案。

如果你还记得高中时候数学课本上抽奖（抽奖这种做法是不是等概率的）那个案例的话，你会瞬间秒懂。

很简单，把每次选中的数字从N个数字中移除掉，然后剩下的再选不就可以了么，就是这么个做法。但是别高兴太早，这里的“移除”还是有讲究的，咋移除，直接拿走，然后把这个数字后面的统统向前移动。这种做法貌似还是有瑕疵，因为这是在让计算机解决问题，不是让人抽奖，抽完直接走人，计算机会为移动数字花费不少时间，有没有更好的做法呢？

答案是肯定的，但也是相当简单的，就一句话，每次选中的元素跟当前选择长度的最后一个元素做交换，即可。

啥意思呢，最开始N个数字，第一次选了a[i]，那么就将a[i]与a[n-1]做交换，然后呢，再从a[0, 1, 2,….., n-2]中再随机选择，如果选中了a[k]，那么就将a[k]与a[n-2]做交换，然后从a[0, 1, 2,….., n-3]中再随机选择……直到选够M个数字，取出最后M个数字即可。这么做就省去了移动的时间成本，时间复杂度为O(n)，终于完工了。

还有没有更绝的，有当然有，学过排列组合吧，这里所选的随机数字无非就是这些数字组合中的一个，那么把所有的组合提前算好不就行了么，然后要的时候，随机取一个组合，时间复杂度为O(1)，完美！

问题本身没那么简单，答案呢也没想象中的那么难，

转载地址：http://vwhii.baihongyu.com/