问题描述

写一个摇号程序，输入是 users 和 quota：

• users 是一个字典，key 是用户名，value 是摇中概率（1 - 99 之间的数值）
• quota 用于指定摇出多少用户

解题思路

1. 将所有用户信息放到列表中，列表的结构如下：

2. 生成一个 [0, total length - 1] 之间的随机数 n
3. 找到节点 node，它需要满足：node.start_index <= n <= node.end_index
4. 将 node.name 加入结果列表；修改 total length；修改 node 之后的所有节点的起始索引和终止索引；从列表中弹出 node
5. 如果结果列表的长度达到 quota，则返回结果列表；否则，回到步骤 2

Python 实现

xxxxxxxxxx
# coding: utf8
​
import random
​
​
class Node(object):
    def __init__(self, start_index, end_index, name):
        self.start_index = start_index
        self.end_index = end_index
        self.name = name
        self.chance = end_index - start_index + 1
​
    def __str__(self):
        return "Node{name=%s, start_index=%d, end_index=%d, chance=%d}" % (
            self.name,
            self.start_index,
            self.end_index,
            self.chance)
​
    __repr__ = __str__
​
​
def lot(users, quota):
    if len(users) <= quota:
        return users.keys()
​
    total_length = 0
    start_index = 0
    user_list = []
    for name, chance in users.iteritems():
        total_length = total_length + chance
        end_index = start_index + chance - 1
        user_list.append(Node(start_index, end_index, name))
        start_index = end_index + 1
​
    chosen = []
    while len(chosen) < quota:
        # 生成一个 [0, total_length-1] 之间的随机数
        n = random.randint(0, total_length - 1)
​
        # 判断谁中奖了
        ind = None
        for ind, node in enumerate(user_list):
            if node.start_index <= n <= node.end_index:
                break
        node = user_list[ind]
        chosen.append(node.name)
​
        # 修改 total_length
        total_length = total_length - node.chance
        # 修改 user_list
        user_list.pop(ind)
        for i in range(ind, len(user_list)):
            user_list[i].start_index -= node.chance
            user_list[i].end_index -= node.chance
    return chosen
​
​
def test():
    # map `name` to `chance`
    users = {"Tim": 2, "Lorriane": 2, "YuNai": 10}
    print(lot(users, 2))
​
​
if __name__ == "__main__":
    test()
​