Python3 Binary Search Without Using Probabilities
I saw many people posted solutions based on probabilities not finding the real majority elements. Here is one without using any of these tricks and it passed OJ
I saw many people posted solutions based on probabilities not finding the `real` majority elements. Here is one without using any of these tricks and it passed OJ fine. Actually it is very fast, beating 98% python submissions so far.\n\nRuntime: 508 ms, faster than 98.52% of Python3 online submissions for Online Majority Element In Subarray.\nMemory Usage: 21 MB, less than 100.00% of Python3 online submissions for Online Majority Element In Subarray.\n\nOne optimizaitons is to always search from the most frequent number, and early terminate when \n` len(self.loc[n]) < threshold`\n\n```\nclass MajorityChecker:\n    def __init__(self, arr: List[int]):\n        self.loc = collections.defaultdict(list)\n        for i, n in enumerate(arr):\n            self.loc[n].append(i)    \n        self.nums = sorted(self.loc.keys(), key = lambda n: len(self.loc[n]), reverse=True)\n        \n    def query(self, left: int, right: int, threshold: int) -> int:\n        for n in self.nums:\n            if len(self.loc[n]) < threshold: return -1\n            l, r = bisect.bisect_left(self.loc[n], left), bisect.bisect_right(self.loc[n], right)\n            if r - l >= threshold: return n\n        return -1\n```
[]