带权重的随机选择算法
Info
已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~
读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
| LeetCode | Difficulty |
|---|---|
| 528. Random Pick with Weight | 🟠 |
Prerequisites
Before reading this article, you should learn:
The reason I wrote this article is because of playing the LOL mobile game. A friend of mine complained that the teammates he gets matched with in ranked games are too weak. I said that I find my teammates in ranked games quite competent, and they don't seem to be a burden.
My friend said meaningfully: "Usually, players with a high hidden score, if they can't get matched with equally skilled teammates, will end up with some weak players."
Huh? I thought for a few seconds and felt something was off. Was he implying that my hidden score is low, or that I am one of those weak players?
I immediately challenged him to a game to prove that I'm not the weak one, but he is. The result of our game won't be disclosed here, so you can guess.
After the game, I started writing this article because I had some thoughts about the game's matching mechanism.
This so-called "hidden score" might not be real, after all, the matching mechanism is a core component of all competitive games and must be very complex, not something that can be determined by a few simple metrics.
However, if we simplify this "hidden score" mechanism, it becomes an interesting algorithm problem: How does the system match players with different random probabilities?
Or to put it simply, how do you make a weighted random choice?
Don't think this is easy. If you have an array of length n and you need to randomly select an element with equal probability, you would know how to do it: just generate a random number between [0, n-1] as the index. Each element has a probability of 1/n to be selected.
But what if each element has a different weight, where the weight represents the probability of that element being randomly selected? How would you write an algorithm to randomly pick an element?
LeetCode problem 528 "Random Pick with Weight" is exactly this kind of problem:
528. Random Pick with Weight | 力扣 | LeetCode |
You are given a 0-indexed array of positive integers w where w[i] describes the weight of the ith index.
You need to implement the function pickIndex(), which randomly picks an index in the range [0, w.length - 1] (inclusive) and returns it. The probability of picking an index i is w[i] / sum(w).
- For example, if
w = [1, 3], the probability of picking index0is1 / (1 + 3) = 0.25(i.e.,25%), and the probability of picking index1is3 / (1 + 3) = 0.75(i.e.,75%).
Example 1:
Input ["Solution","pickIndex"] [[[1]],[]] Output [null,0] Explanation Solution solution = new Solution([1]); solution.pickIndex(); // return 0. The only option is to return 0 since there is only one element in w.
Example 2:
Input ["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"] [[[1,3]],[],[],[],[],[]] Output [null,1,1,1,1,0] Explanation Solution solution = new Solution([1, 3]); solution.pickIndex(); // return 1. It is returning the second element (index = 1) that has a probability of 3/4. solution.pickIndex(); // return 1 solution.pickIndex(); // return 1 solution.pickIndex(); // return 1 solution.pickIndex(); // return 0. It is returning the first element (index = 0) that has a probability of 1/4. Since this is a randomization problem, multiple answers are allowed. All of the following outputs can be considered correct: [null,1,1,1,1,0] [null,1,1,1,1,1] [null,1,1,1,0,0] [null,1,1,1,0,1] [null,1,0,1,0,0] ...... and so on.
Constraints:
1 <= w.length <= 1041 <= w[i] <= 105pickIndexwill be called at most104times.
Let's think about this problem and solve the issue of randomly selecting elements based on weights.