工作需要，這兩天寫一個(gè)簡(jiǎn)單的java抽獎(jiǎng)算法，因?yàn)檫壿嫼?jiǎn)單不復(fù)雜，所以代碼也很簡(jiǎn)潔，可以做到不同權(quán)重有不用的中獎(jiǎng)概率（就類似于nginx集群一樣，權(quán)重越大，概率越高），在這里將java概率隨機(jī)抽獎(jiǎng)代碼抽離出來分享給大家。

具體需求：

給第三方推送數(shù)據(jù)，每個(gè)第三方根據(jù)預(yù)算會(huì)有不同的額度，考慮到服務(wù)器壓力，所以采取了主動(dòng)推送的方式，在每次推送的時(shí)候，需要根據(jù)第三方的配額計(jì)算出相應(yīng)的概率，然后挑選一個(gè)第三方來推送。

思路分析：

從形式上看，跟隨機(jī)抽獎(jiǎng)幾乎一模一樣，都是在N中挑選1，而且還不是公平挑選，是帶有概率性的。

由于只分享概率隨機(jī)抽獎(jiǎng)的算法，所以就暫不考慮上限的情況，簡(jiǎn)單的說一下算法部分的實(shí)現(xiàn)思路（重點(diǎn)在于計(jì)算概率和區(qū)間，我這里是數(shù)量固定，所以概率很好算，具體真實(shí)的抽獎(jiǎng)業(yè)務(wù)中會(huì)很復(fù)雜）。

1、需要計(jì)算出每個(gè)第三方的配額在總配額中的占比情況：自身數(shù)量 / 總數(shù)量 = 各自占比；

2、用100來做隨機(jī)區(qū)間（1也可以），計(jì)算出每個(gè)區(qū)間的隨機(jī)數(shù)值跨度：比例 * 100 = 區(qū)間跨度；

3、根據(jù)跨度計(jì)算出每個(gè)區(qū)間的起始數(shù)值：從0開始按照每個(gè)跨度相加，最終將100拆分成N個(gè)區(qū)間；

代碼實(shí)現(xiàn)：

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;

/**
 * Created by Felix on 2019/07/10.
 */
public class Lottery {

    /**
     * 計(jì)算自身相對(duì)于總體的比例
     *
     * @param self 自身
     * @param all  總體
     * @return 比例
     */
    private static float getPercent(Integer self, Integer all) {
        // 比例計(jì)算出來會(huì)有很多小數(shù)，為了看得清晰，要四舍五入一下
        return new BigDecimal(self / all.floatValue()).setScale(2, BigDecimal.ROUND_HALF_UP).floatValue();
    }

    /**
     * 根據(jù)比例，在100之間計(jì)算出區(qū)間跨度，進(jìn)一步來計(jì)算中獎(jiǎng)區(qū)間
     *
     * @param percent 比例
     * @return 跨度
     */
    private static int getRandom(float percent) {
        // 如果getPercent中沒有四舍五入，那么就需要在這里四舍五入
        return new BigDecimal(percent * 100).intValue();
    }

    private void lottery() {

        Integer allAmount = 233;// 總配額（抽獎(jiǎng)總次數(shù)）

        List<User> users = new ArrayList<>();
        users.add(new User(1, "張三", 11));
        users.add(new User(2, "李四", 22));
        users.add(new User(3, "王五", 5));
        users.add(new User(4, "趙六", 111));
        users.add(new User(5, "田七", 66));
        users.add(new User(6, "陳八", 18));

        Map<Integer, Offset> userOffsetMap = new HashMap<>();
        float percent;// 比例
        int span;// 跨度
        int start = 0;// 區(qū)間開始
        int end;// 區(qū)間結(jié)束
        for (User user : users) {
            percent = getPercent(user.getAmount(), allAmount);
            span = getRandom(percent);
            // 按照跨度計(jì)算offset
            end = start + span;
            userOffsetMap.put(user.getId(), new Offset(percent, span, start, end, user.getAmount()));
            // 因?yàn)閰^(qū)間不能超過100，所以每次都需要用新的數(shù)值+跨度
            start = end;
        }

        // log
        for (Integer userId : userOffsetMap.keySet()) {
            Offset offset = userOffsetMap.get(userId);
            System.out.println("用戶: " + userId + ", 配額: " + offset.getAmount() + ", 占比: " + offset.getPercent() + ", 跨度: " + offset.getSpan() + ", 區(qū)間: [" + offset.getStart() + ", " + offset.getEnd() + ")");
        }

        Map<Integer, Integer> countMap = new HashMap<>();
        Integer userId;
        Integer num;
        for (int i = 0; i < allAmount; i++) {
            // 由于這里是遞歸處理，所以如果最后為null了，說明已經(jīng)到達(dá)了所有人的配額上限（獎(jiǎng)品或者抽獎(jiǎng)次數(shù)用完了）
            userId = randomUser(userOffsetMap);
            if (userId == null) {
                break;
            }
            // 記錄每個(gè)用戶的中標(biāo)次數(shù)，達(dá)到上限了就排除掉
            num = countMap.get(userId);
            if (num != null) {
                countMap.put(userId, num + 1);
            } else {
                countMap.put(userId, 1);
            }
            // 次數(shù)到了上限，移除用戶（可看做：中獎(jiǎng)之后移除用戶）
            if (countMap.get(userId) >= userOffsetMap.get(userId).getAmount()) {
                userOffsetMap.remove(userId);
            }
        }

        // log
        for (Integer key : countMap.keySet()) {
            System.out.println(key + "中獎(jiǎng)了" + countMap.get(key) + "次，概率: " + getPercent(countMap.get(key), allAmount));
        }
    }

    /**
     * 選中之后，會(huì)排除掉部分用戶，遞歸調(diào)用，將機(jī)會(huì)讓給別的人
     *
     * @param userOffsetMap 用戶offset信息
     * @return 選中的用戶
     */
    private Integer randomUser(Map<Integer, Offset> userOffsetMap) {
        Integer userId = select(userOffsetMap);
        if (!userOffsetMap.isEmpty() && userId == null) {
            return randomUser(userOffsetMap);
        }
        return userId;
    }

    /**
     * 按照計(jì)算好的區(qū)間，隨機(jī)獲取用戶（即視為中標(biāo)了）
     *
     * @param userOffsetMap 用戶offset信息
     * @return 選中的用戶
     */
    private Integer select(Map<Integer, Offset> userOffsetMap) {
        // 計(jì)算一個(gè)隨機(jī)數(shù)值，看他散列在哪個(gè)用戶的區(qū)間
        int rnum = new Random().nextInt(100);
        Offset offset;
        // 由于要兼顧每一個(gè)用戶，所以需要循環(huán)（效率待定？）
        for (Integer userId : userOffsetMap.keySet()) {
            offset = userOffsetMap.get(userId);
            // 100以內(nèi)隨機(jī)，所以需要是左側(cè)需要等于，右側(cè)不需要
            if (offset.getStart() <= rnum && rnum < offset.getEnd()) {
                return userId;
            }
        }
        return null;
    }

    public static void main(String[] args) {
        new Lottery().lottery();
    }

    class User {

        private int id;
        private String name;
        private int amount;

        public User(int id, String name, int amount) {
            this.id = id;
            this.name = name;
            this.amount = amount;
        }

        public int getId() {
            return id;
        }

        public void setId(int id) {
            this.id = id;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        public int getAmount() {
            return amount;
        }

        public void setAmount(int amount) {
            this.amount = amount;
        }
    }

    class Offset {

        private float percent;
        private int span;
        private int start;
        private int end;
        private int amount;

        public Offset(float percent, int span, int start, int end, int amount) {
            this.percent = percent;
            this.span = span;
            this.start = start;
            this.end = end;
            this.amount = amount;
        }

        public float getPercent() {
            return percent;
        }

        public void setPercent(float percent) {
            this.percent = percent;
        }

        public int getSpan() {
            return span;
        }

        public void setSpan(int span) {
            this.span = span;
        }

        public int getStart() {
            return start;
        }

        public void setStart(int start) {
            this.start = start;
        }

        public int getEnd() {
            return end;
        }

        public void setEnd(int end) {
            this.end = end;
        }

        public int getAmount() {
            return amount;
        }

        public void setAmount(int amount) {
            this.amount = amount;
        }
    }

}

實(shí)現(xiàn)效果：

用java實(shí)現(xiàn)簡(jiǎn)單的概率隨機(jī)抽獎(jiǎng)算法

跟代碼中的參數(shù)做一下簡(jiǎn)單比對(duì)，總配額是233次（可視作為233次抽獎(jiǎng)機(jī)會(huì)），6個(gè)用戶按照不同比例分配不同的配額，全部抽獎(jiǎng)完成之后看到的概率與配額的比例是一致的，說明按概率隨機(jī)抽取成功！
最后給大家贈(zèng)送一本書籍《數(shù)據(jù)結(jié)構(gòu)與算法經(jīng)典問題解析》豆瓣評(píng)分8.6 需要的朋友可以來簡(jiǎn)信我領(lǐng)取

用java代碼實(shí)現(xiàn)簡(jiǎn)單的概率隨機(jī)抽獎(jiǎng)算法，看完相信你也會(huì)

本書的目的是使讀者知曉數(shù)據(jù)結(jié)構(gòu)和算法的設(shè)計(jì)原理和實(shí)現(xiàn)，而并非單純地講述定理及證明。為此，本書利用不同的復(fù)雜度來改善問題的解。對(duì)于許多問題，從窮舉解法開始，逐步引入問題的最佳解，并給出算法所需的運(yùn)行時(shí)間和空間。

全書包含4個(gè)部分，第一部分（第1?2章）主要描述抽象數(shù)據(jù)類型，給出算法的基本概念和復(fù)雜度分析與評(píng)價(jià)方法，并討論幾乎每章都要用到的遞歸和回溯技術(shù)

第二部分（第3?9章）介紹基本數(shù)據(jù)結(jié)構(gòu)，包括鏈表、棧、隊(duì)列、樹、優(yōu)先隊(duì)列、堆、并査集和圖，對(duì)于每一種數(shù)據(jù)結(jié)構(gòu)分別采用多個(gè)實(shí)例進(jìn)行具體的演示。

第三部分（第10-15章）介紹數(shù)據(jù)處理的技術(shù)，包括排序、査找、選擇、符號(hào)表、散列和字符串算法。

第四部分（第16?21章）重點(diǎn)介紹一些常用的算法設(shè)計(jì)技術(shù)及應(yīng)用，包括貪婪算法、分治算法、動(dòng)態(tài)規(guī)劃算法、復(fù)雜度類型，并討論對(duì)于面試和考試的一些有用話題。本書強(qiáng)調(diào)問題及分析，而不側(cè)重于理論?？梢宰鳛閺氖掠?jì)算機(jī)研究與開發(fā)的技術(shù)人員的參考書，特別是對(duì)正在準(zhǔn)備面試、參加選拔性考試以及校園面試的讀者尤為有用。

不想把篇幅拉的太長(zhǎng)需要的朋友可以來私信領(lǐng)取

書籍免費(fèi)獲取方式：關(guān)注然后簡(jiǎn)信“資料”即可獲得文檔領(lǐng)取方式

同時(shí)希望大家領(lǐng)到之后不要做收藏黨！而是能夠花一些時(shí)間認(rèn)真看完文檔，讓它真正發(fā)揮出價(jià)值來。

用java代碼實(shí)現(xiàn)簡(jiǎn)單的概率隨機(jī)抽獎(jiǎng)算法，看完相信你也會(huì)

用java代碼實(shí)現(xiàn)簡(jiǎn)單的概率隨機(jī)抽獎(jiǎng)算法，看完相信你也會(huì)