710. Random Pick with Blacklist via Hash map
Here we create the hash map to map elements in the blacklist into the whitelist. Suppose the length of the whitelist is whiteSize. We randomly generate an integ
Here we create the hash map to map elements in the blacklist into the whitelist. Suppose the length of the whitelist is **whiteSize**. We randomly generate an integer **index** in the interval **[0, whiteSize)** at first. If the integer **index** is in the hash map we created before, we can use this map to transform this **index** to another index corresponding to an element in the whitelist.\n```\nclass Solution:\n\tdef __init__(self, n, blacklist):\n\t\tself.whiteSize = n - len(blacklist)\n\t\tself.hmap = {ele: 1 for ele in blacklist}\n\t\t\n\t\tidx = n - 1\n\t\tfor ele in self.hmap:\n\t\t\tif ele >= self.whiteSize:\n\t\t\t\tcontinue\n\t\t\t\n\t\t\twhile idx in self.hmap:\n\t\t\t\tidx -= 1\n\t\t\tself.hmap[ele] = idx\n\t\t\tidx -= 1\n\t\t\t\n\tdef pick(self):\n\t\tindex = randint(0, self.whiteSize - 1)\n\t\tif index in self.hmap:\n\t\t\treturn self.hmap[index]\n\t\treturn index\n```\nThe idea is to divide **[0, n)** into two parts at the partition point **whiteSize**, where **[0, whiteSize]** ideally is used to store indices of whitelist. However, if there are some elements in the blacklist appearing in **[0, whiteSize]** (which implies definitely there are some elements in the whitelist showing in **[whiteSize, n)**), we use a hash map to construct a connection (a map) between elements incorrectly falling into above 2 sub-intervals around.\n\nOur goal is to map all blacklist elements into the tail of the list [0, n). So for each element in the blacklist, if it is already located at the tail (implies this element is >= **whiteSize**), we do not bother it. However, if it is before **whiteSize**, we want to map it to a value as far back as possible. This is the reason we initialize a reference **idx = n - 1**, and keep decreasing it by 1 after each mapping. However, if this **idx** actually is the element in the blacklist (use **hmap** to make search/check efficient), we need to give up this and decrease it (by using while loop) until it is not a blacklist element any more (mapping a blacklist element to a blacklist element does not make sense).\n\nOnce we finish creating this map, we are ready for multiple downstream jobs -- pick. If the number we generate is exactly the whitelist element, we directly return it. Otherwise, call the hash map.\n\nSuppose the length of the blacklist is n. Then the time complexity is O(n) since we are trying to construct a map for each blacklist element, and hence the space complexity is O(n).\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
['Hash Table', 'Python3']