工作需要，这两天写一个简单的java抽奖算法，因为逻辑简单不复杂，所以代码也很简洁，可以做到不同权重有不用的中奖概率（就类似于nginx集群一样，权重越大，概率越高），在这里将java概率随机抽奖代码抽离出来分享给大家。
具体需求：
给第三方推送数据，每个第三方根据预算会有不同的额度，考虑到服务器压力，所以采取了主动推送的方式，在每次推送的时候，需要根据第三方的配额计算出相应的概率，然后挑选一个第三方来推送。
思路分析：
从形式上看，跟随机抽奖几乎一模一样，都是在N中挑选1，而且还不是公平挑选，是带有概率性的。
由于只分享概率随机抽奖的算法，所以就暂不考虑上限的情况，简单的说一下算法部分的实现思路（重点在于计算概率和区间，我这里是数量固定，所以概率很好算，具体真实的抽奖业务中会很复杂）。
1、需要计算出每个第三方的配额在总配额中的占比情况：自身数量 / 总数量 = 各自占比；
2、用100来做随机区间（1也可以），计算出每个区间的随机数值跨度：比例 * 100 = 区间跨度；
3、根据跨度计算出每个区间的起始数值：从0开始按照每个跨度相加，最终将100拆分成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 {
/**
* 计算自身相对于总体的比例
*
* @param self 自身
* @param all 总体
* @return 比例
*/
private static float getPercent(Integer self, Integer all) {
// 比例计算出来会有很多小数，为了看得清晰，要四舍五入一下
return new BigDecimal(self / all.floatValue()).setScale(2, BigDecimal.ROUND_HALF_UP).floatValue();
}
/**
* 根据比例，在100之间计算出区间跨度，进一步来计算中奖区间
*
* @param percent 比例
* @return 跨度
*/
private static int getRandom(float percent) {
// 如果getPercent中没有四舍五入，那么就需要在这里四舍五入
return new BigDecimal(percent * 100).intValue();
}
private void lottery() {
Integer allAmount = 233;// 总配额（抽奖总次数）
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;// 区间开始
int end;// 区间结束
for (User user : users) {
percent = getPercent(user.getAmount(), allAmount);
span = getRandom(percent);
// 按照跨度计算offset
end = start + span;
userOffsetMap.put(user.getId(), new Offset(percent, span, start, end, user.getAmount()));
// 因为区间不能超过100，所以每次都需要用新的数值+跨度
start = end;
}
// log
for (Integer userId : userOffsetMap.keySet()) {
Offset offset = userOffsetMap.get(userId);
System.out.println("用户: " + userId + ", 配额: " + offset.getAmount() + ", 占比: " + offset.getPercent() + ", 跨度: " + offset.getSpan() + ", 区间: [" + offset.getStart() + ", " + offset.getEnd() + ")");
}
Map<Integer, Integer> countMap = new HashMap<>();
Integer userId;
Integer num;
for (int i = 0; i < allAmount; i++) {
// 由于这里是递归处理，所以如果最后为null了，说明已经到达了所有人的配额上限（奖品或者抽奖次数用完了）
userId = randomUser(userOffsetMap);
if (userId == null) {
break;
}
// 记录每个用户的中标次数，达到上限了就排除掉
num = countMap.get(userId);
if (num != null) {
countMap.put(userId, num + 1);
} else {
countMap.put(userId, 1);
}
// 次数到了上限，移除用户（可看做：中奖之后移除用户）
if (countMap.get(userId) >= userOffsetMap.get(userId).getAmount()) {
userOffsetMap.remove(userId);
}
}
// log
for (Integer key : countMap.keySet()) {
System.out.println(key + "中奖了" + countMap.get(key) + "次，概率: " + getPercent(countMap.get(key), allAmount));
}
}
/**
* 选中之后，会排除掉部分用户，递归调用，将机会让给别的人
*
* @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;
}
/**
* 按照计算好的区间，随机获取用户（即视为中标了）
*
* @param userOffsetMap 用户offset信息
* @return 选中的用户
*/
private Integer select(Map<Integer, Offset> userOffsetMap) {
// 计算一个随机数值，看他散列在哪个用户的区间
int rnum = new Random().nextInt(100);
Offset offset;
// 由于要兼顾每一个用户，所以需要循环（效率待定？）
for (Integer userId : userOffsetMap.keySet()) {
offset = userOffsetMap.get(userId);
// 100以内随机，所以需要是左侧需要等于，右侧不需要
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;
}
}
}
实现效果：
跟代码中的参数做一下简单比对，总配额是233次（可视作为233次抽奖机会），6个用户按照不同比例分配不同的配额，全部抽奖完成之后看到的概率与配额的比例是一致的，说明按概率随机抽取成功！
最后给大家赠送一本书籍《数据结构与算法经典问题解析》豆瓣评分8.6 需要的朋友可以来简信我领取
本书的目的是使读者知晓数据结构和算法的设计原理和实现，而并非单纯地讲述定理及证明。为此，本书利用不同的复杂度来改善问题的解。对于许多问题，从穷举解法开始，逐步引入问题的最佳解，并给出算法所需的运行时间和空间。
全书包含4个部分，第一部分（第1〜2章）主要描述抽象数据类型，给出算法的基本概念和复杂度分析与评价方法，并讨论几乎每章都要用到的递归和回溯技术
第二部分（第3〜9章）介绍基本数据结构，包括链表、栈、队列、树、优先队列、堆、并査集和图，对于每一种数据结构分别采用多个实例进行具体的演示。
第三部分（第10-15章）介绍数据处理的技术，包括排序、査找、选择、符号表、散列和字符串算法。
第四部分（第16〜21章）重点介绍一些常用的算法设计技术及应用，包括贪婪算法、分治算法、动态规划算法、复杂度类型，并讨论对于面试和考试的一些有用话题。本书强调问题及分析，而不侧重于理论。可以作为从事计算机研究与开发的技术人员的参考书，特别是对正在准备面试、参加选拔性考试以及校园面试的读者尤为有用。
不想把篇幅拉的太长需要的朋友可以来私信领取
书籍免费获取方式：关注然后简信“资料”即可获得文档领取方式
同时希望大家领到之后不要做收藏党！而是能够花一些时间认真看完文档，让它真正发挥出价值来。
