[leetcode]710. Random Pick with Blacklist Problem Solving Report - Programmer Sought

[leetcode]710. Random Pick with Blacklist Problem Solving Report - Programmer Sought

Given N, and a blacklist array, each time a random number is selected from [0, N), the random number cannot exist in the blacklist.
Idea:
The number of random numbers in the final result is definitelyN-len(blacklist), so we have to choose the last random value, one is to map the value in the blacklist to the whitelist
The number of random numbers in the result isN-len(blacklist), then we must first take the array [0, N] beforeN-len(blacklist)Elements, but before thisN-len(blacklist)What if there are elements in the blacklist? We use a pointer to scan the array from back to front. If the latter value is not in the blacklist and the previous value is in the blacklist, replace the previous one with the following value.
After the above operation, we will range from randomNShrinked toN- len(blacklist)In the range of size, save it with a map, the key is1~N-len(blacklist), the value is the number in the white list

Read full article from [leetcode]710. Random Pick with Blacklist Problem Solving Report - Programmer Sought