求解概率均等的随机数

Question

随机返回0到n中非m的整数，只调用一次rand，概率均等
int f = rand()
如何让f变为[0，n)中非m的整数，要概率均等，mE[0,n)
当时面试官说用概率做，分布到n-1个数上，然后交换位置什么的，完全没听懂

Answer 1

就是说，随机到m的时候，这个数不能要，要把它变成别的数
既然要概率均等，那么如果你一开始就随机的是[0，n)，那么m变成任何别的数，那个数的概率就会加倍
所以一开始就要随机[0，n-1)的范围，遇到m就把它改成n-1，这样概率就均等了
当然你也可以一开始随机[1,n)，遇到m变0
-=-=-=-=-=
其实这道题答案是什么根本不重要
重要的是遇到一个问题的时候如何思考
如果题目只告诉你[0，n)范围随机，这题就太简单了
而m不要，它会有什么问题，要从问题出发
如果可以随机多次，那么随机到m就重新随机，这没有问题
而如果只能随机一次，随机到m的时候你总不能丢弃吧，要把它变成另一个数返回
思考到这里答案基本已经很显而易见了
要么你把m变成0，要么把m变成n-1，要么把m变成m+1，答案并不唯一，但是思路其实是一样的