Alias method

Leetcode: Random Pick with weight
alias method 算法流程总结：

import numpy as np
int k = len(probs)
q=np.zeros(K)
J=np.zeros(K,dtype=np.int)
for kk, prob in enumerate(self.probs):
    self.q[kk] = prob* self.K
    if self.q[kk] < 1.0:
        self.smaller.append(kk)
    else:
        self.larger.append(kk)
while len(self.smaller)>0 and len(self.larger)>0:
    small = self.smaller.pop()
    large = self.larger.pop()
    self.J[small] = large
    self.q[large] = self.q[large] - (1-self.q[small])
    if self.q[large] < 1.0:
         self.smaller.append(large)
    else:
         self.larger.append(large)

def pickIndex(self):
    sz = len(self.J)
    kk = int(np.floor(np.random.rand())*sz)
    if np.random.rand() < q[kk]:
        return kk
    else:
        return J[kk]