# 狗狗店面1018

Design a class to return a query based on its probability.
Input: dictionary with key = query_name, value = probability
Eg. {a: 0.5, b: 0.2, c: 0.2, d: 0.1}
Output: a or b or c or d with probability stated in the input

a: 0.5, b: 0.2, c: 0.2, d: 0.1

Create 一个array 出现几次就有几个元素 arr = [a,a,a,a,a,b,b,c,c,d];
Random rd = new Random;
int index = rd.nextInt(arr.length());
return arr[index];

``````
// refer to https://tinyurl.com/ybjqfpqy       https://tinyurl.com/ycsc9nlz

import java.util.*;
public class getWithRandom {
public static void main(String[] args){
Map<String, Double> myMap = new HashMap<>();
myMap.put("a", 0.55);
myMap.put("b", 0.1);
myMap.put("c", 0.2);
myMap.put("d", 0.15);
DistributedRandomStringGenerator q = new DistributedRandomStringGenerator(myMap);
List<String> ans = new ArrayList<>();
for(int i=0; i<10000; i++)
// verify our result
Map<String, Integer> countMap = new HashMap<>();
for(String n : ans)
countMap.put(n, 1 + countMap.getOrDefault(n, 0));

for(Map.Entry<String, Integer> entry : countMap.entrySet())
System.out.println(entry.getKey() + ": " + ((double)entry.getValue() / ans.size()));
}

}

class DistributedRandomStringGenerator{
private Random rand;
private double[] cumulative;
private String[] sArray;
DistributedRandomStringGenerator(Map<String, Double> probMap){
rand = new Random();
cumulative = new double[probMap.size()];
sArray = new String[probMap.size()];
int i = 0;
for(Map.Entry<String, Double> entry : probMap.entrySet()){
// we don''t want those string whose probability is less than or equal to zero
if(entry.getValue() > 0){
sArray[i] = entry.getKey();
cumulative[i] = entry.getValue() + (i > 0 ? cumulative[i - 1] : 0);
i++;
}
}
}

String getRandomString(){
double r = rand.nextDouble();
int index = binarySearch(r);
return sArray[index];
}

private int binarySearch(double r){
int low = 0, high = cumulative.length - 1;
while(low + 1 < high){
int mid = low + ((high - low) >> 1);
if(cumulative[mid] == r)
return mid;
else if(cumulative[mid] < r)
low = mid;
else
high = mid;
}
if(r > cumulative[low])
return high;
return low;
}
}
``````

{a: 0.5, b: 0.2, c: 0.2, d: 0.1} 为例，可不可以：1.按50%概率决定是否要a，如果决定要，return a 2.如果决定不要，按0.2/(1-0.5)的概率决定要不要b, 如要，return b. 3.如果不要b，按0.2/(1-0.5-0.2)的概率决定要不要c，以此类推…这样总体来说选a概率是1/2, 选b的概率是1/2 * 2/5 = 1/5, 选c的概率是1/2 * 3/5 * 2/3 = 1/5…