這道題應該算是我原創的的一道題，來源于我遇到的一個具體需求，大致需求是已知一批數和每個數出現的次數，然后寫個介面，每次呼叫都能回傳已知資料中的某個數，且回傳的概率和原始資料中每個數出現的概率一致，題目描述起來有些繞口，我們來舉個實際的例子，
以上面的輸入為例，要求實作的介面必須以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[]替代其功能？
CSDN認證博客專家
Linux
分布式
Spring
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/55690.html
標籤：其他
上一篇：java實作坦克大戰(功能豐富)