这道题应该算是我原创的的一道题，来源于我遇到的一个具体需要。大抵需要是已知一批数和每个数呈现的次数，而后写个接口，每次调用都能返回已知数据中的某个数，且返回的概率和原始数据中每个数呈现的概率统一，题目形容起来有些绕口，咱们来举个理论的例子。
以下面的输出为例，要求实现的接口必须以11.96%的概率返回5、18.10%的概率返回91……16.55%的概率返回98，当然我的要求不仅仅是这几个数，而是可能有10^5个数。 先别急着往下看，给你几分钟先思考下。
各种语言其实都内置了random函数，能够随机返回int或者long型的随机数，这里咱们先不思考溢出的问题。为了不便解说，假如咱们已有n个数存在在num[n]中，其呈现的频次寄存在fre[n]中。 借助已有的random()，咱们很简略就能够生成0-n之间的一个随机数i，然而如果间接返回num[i]的话，每个数返回的概率是统一的，显著不满足咱们的需要。
其实解决方案也很简略，咱们依照每个数呈现的频次大小，将其映射成不同的区间大小，呈现的概率越大，区间越大。设想下，这些数据按不同的区间大小把一个飞镖盘分成不同的局部，咱们生成数的时候就是拿个飞镖随机扎，扎到哪个算哪个。
当然咱们能够间接用一位直线区间形容下面的二维飞镖盘模型。只须要随机生成0-100%之间的数即可，假如某次随机生成的数是0.65(65%)，咱们算一下 正好对应在数字58对应的区间上，所以这次间接返回58就是了，咱们能够开始写代码了。
int[] num; // 数字 int[] fre; // 呈现的频次 double[] pro; // 呈现的概率 int n; // 数据量 void init() { int sum = 0; for (int i = 0; i < n; i++) { sum += fre[i]; } for (int i = 0; i < n; i++) { pro[i] = fre[i]/sum; // 计算出每个数呈现的概率 } } int getRandom() { double rp = random.getNextDouble(); double sum = 0; for (int i = 0; i < n; i++) { if (sum >= r && sum + pro[i] > rp) { //找到命中的区间 return num[i]; } sum += pro[i]; } return num[n-1]; }仿佛所有都很完满，但每次getRandom()的工夫复杂度是O(n)，大量的使用性能也抗不太住。有没有更好的实现形式？既然写到这里了，必然是有的。
下面代码循环中有个sum += pro[i]; 每次计算都要累加，咱们是不是能够提前在init()中累加好？而后你会发现因为每次累加的数都只负数，所以pro是个递增序列，对于有序序列的查找 二分必然是首选。这时候咱们能够用二分重写下面代码。
int[] num; // 数字 int[] fre; // 呈现的频次 double[] pro; // 呈现的概率 int n; // 数据量 void init() { int sum = 0; for (int i = 0; i < n; i++) { sum += fre[i]; } for (int i = 0; i < n; i++) { pro[i] = fre[i]/sum; // 计算出每个数呈现的概率 if (i != 0) { pro[i] += pro[i-1]; } } } int getRandom() { double rp = random.getNextDouble(); int l = 0; int r = n-1; while (l != r) { // 二分查找确定区间地位 int mid = (l + r) >> 1; if (pro[mid] < rp) { l = mid + 1; } else { r = mid; } } return num[n-1]; }到这里问题就彻底解决了，然而最初给大家留下一个思考题。
上述代码中pro[]的计算有必要吗？ 是否间接用fre[]代替其性能？