leetcode：710. Random numbers in the blacklist [mapping thinking]

analysis

Let's give a boundary first bound We hope that all blacklists can be mapped to bound（ Include ） The position after
If the blacklist had been bound Back , We just put it in black in
Then traverse the rest of the blacklist , If you find that , It's in bound front
We from bound Start with the value of , Start traversing backwards one by one , Find the first non blacklist location w
Then make b2w[b] = w This completes the mapping from blacklist to whitelist
And then finally use a random one [0, bound - 1] Number of numbers
If there is no mapping , That means it's a white list ; If there is an insinuation , Find the corresponding white list

ac code

class Solution:
    def __init__(self, n: int, blacklist: List[int]):
        m = len(blacklist)
        self.bound = w = n - m

        #  hypothesis bound There are blacklists in the back , There are white lists ahead 
        black = {
    b for b in blacklist if b >= self.bound}
        self.b2w = {
    }
        for b in blacklist:
            #  If you encounter a blacklist 
            if b < self.bound:
                #  Find the space in the back 
                while w in black:
                    w += 1
                #  Put the current blacklist   mapping   to   White list of corresponding positions 
                self.b2w[b] = w
                #  Next position 
                w += 1
        #print(self.b2w)

    def pick(self) -> int:
        x = randrange(self.bound) #  Excluding the right endpoint , from 0 Start , In steps of 1
        #x = randint(0, self.bound - 1)
        return self.b2w.get(x, x) #  If it's not a blacklist , Just choose yourself ; Otherwise, select the mapped white list 

summary

Blacklist mapping method , Make according to the former bound A random case
You can find the value of the white list mapped by the blacklist