[数据结构与算法]【Java实现】带权重的随机数算法

我们按照顺序计算出权重的加和，把当前数字出现的权重加和前的值作为其权重范围的起点值，把加和后的值作为其权重范围的终点值。
这样的话，我们就可以使用Random.next(100)来做随机数，然后判断随机数落在的范围，然后映射到对应的优惠券数值即可。

import java.util.*;
public class WeightRandom {
    private List<WeightElement> weightElements;
    public void initWeight(String[] keys, Integer[] weights){
        if(keys == null || weights == null || keys.length != weights.length){//异常传参情况
            return;
        }
        weightElements = new ArrayList<>();
        for (int i=0; i< keys.length; i++){
            weightElements.add(new WeightElement(keys[i], weights[i]));
        }
        if(weightElements.size() == 0){
            return;
        }
        //初始化后分配各个key中的元素值
        WeightElement ele0 = weightElements.get(0);
        ele0.setThresholdLow(0);
        ele0.setThresholdHigh(ele0.getWeight());
        for (int i = 1; i < weightElements.size(); i++){
            WeightElement curElement = weightElements.get(i);
            WeightElement preElement = weightElements.get(i - 1);
            curElement.setThresholdLow(preElement.getThresholdHigh());
            curElement.setThresholdHigh(curElement.getThresholdLow() + curElement.getWeight());
        }
    }

    //二分查找写法
    public WeightElement getElementByRandomValue(Integer rv){
        if(rv < 0 || rv > getMaxRandomValue()-1){
            return null;
        }
        //此时rv必然在0 - getMaxRandomValue()-1范围内，
        //也就是必然能够命中某一个值
        int start = 0, end = weightElements.size() - 1;
        int index = weightElements.size()/2;
        while(true){
            if(rv < weightElements.get(index).getThresholdLow()){
                end = index - 1;
            }else if(rv >= weightElements.get(index).getThresholdHigh()){
                start = index + 1;
            }else{
                return weightElements.get(index);
            }
            index = (start + end)/2;
        }
    }

    /**非二分查找的写法
    public WeightElement getElementByRandomValue(Integer rv){
        //因为元素权重范围有序递增，所以这里可以改为二分查找
        for (WeightElement e:weightElements){
            if(rv >= e.getThresholdLow() && rv < e.getThresholdHigh()){
                return e;
            }
        }
        return null;
    }**/
    public int getMaxRandomValue(){
        if(weightElements == null || weightElements.size() == 0){
            return 0;
        }
        return weightElements.get(weightElements.size() - 1).getThresholdHigh();
    }
    static class WeightElement{
        //元素标记
        private String key;
        //元素权重
        private Integer weight;
        //权重对应随机数范围下限和上限
        private Integer thresholdLow;
        private Integer thresholdHigh;
        public WeightElement(String key, Integer weight){
            this.key = key;
            this.weight = weight;
        }
        public String getKey() {
            return key;
        }
        public void setKey(String key) {
            this.key = key;
        }
        public Integer getWeight() {
            return weight;
        }
        public void setWeight(Integer weight) {
            this.weight = weight;
        }
        public Integer getThresholdLow() {
            return thresholdLow;
        }
        public void setThresholdLow(Integer thresholdLow) {
            this.thresholdLow = thresholdLow;
        }
        public Integer getThresholdHigh() {
            return thresholdHigh;
        }
        public void setThresholdHigh(Integer thresholdHigh) {
            this.thresholdHigh = thresholdHigh;
        }
        
        public static void main(String[] args){
            WeightRandom wr = new WeightRandom();
            wr.initWeight(new String[]{"1","2","3","4"}
                    , new Integer[]{100,100,200,600});
            Random r = new Random();
            for (int i = 0; i < 10; i++){
                Integer rv = r.nextInt(wr.getMaxRandomValue());
                System.out.println(rv);
                System.out.println(wr.getElementByRandomValue(rv).getKey() + " " + rv);
            }

            //针对随机到的元素个数做一个简单测试
            HashMap<String, Integer> keyCount = new HashMap<String, Integer>();
            keyCount.put("1", 0);
            keyCount.put("2", 0);
            keyCount.put("3", 0);
            keyCount.put("4", 0);
            for (int i = 0; i < 10000; i++){
                Integer rv = r.nextInt(wr.getMaxRandomValue());
                String key = wr.getElementByRandomValue(rv).getKey();
                keyCount.put(key, keyCount.get(key) +1);
            }
            System.out.println(keyCount);
            System.out.println("");
        }
    }
}
```

结果：{1=1018, 2=1008, 3=2081, 4=5893}