leetcode.528 Random Pick with Weight

JS version

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var solution = function(w){
	this.map = new Map();
	this.sum = 0;
	for(let i = 0; i < w.length; i++){
	this.sum += w[i];
	this.map.set(this.sum, i);
	this.keys = [...this.map.keys()].sort((a, b) => a-b);
	}
}

solution.prototype.pickIndex = function(){
	const r = parseInt(Math.random() * this.sum);
	for(const key of this.keys){
		if(r < key){
			return this.map.get(key);
		}
	}
}