LeetCode 1157 通过随机数来碰运气过OJ

发表于

思路：

本题我之前想过是否有什么方法可以过，但似乎没有必定正确的方法。如果有，应该也只是c++和Java的暴力法能过了。

一个取巧的方法，随机在left和right中取100个数，记录这100个数的出现次数。如果数的种类超过3个，只有出现次数大于10的才去判断是否大于阈值。如果种类小于3个，则所有的数都参与判断。

时间复杂段300 O(log n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import collections
import random
import bisect


class MajorityChecker:

    def __init__(self, arr):
        self.array = arr
        self.arr = collections.defaultdict(list)
        for i in range(len(arr)):
            self.arr[arr[i]].append(i)

    def query(self, left: int, right: int, threshold: int) -> int:
        a = collections.defaultdict(int)
        for i in range(100):
            p = self.array[random.randint(left, right)]
            a[p] += 1
        keys = []
        if len(a.keys()) > 3:
            for k in a.keys():
                if a[k] > 10:
                    keys.append(a[k])
        else:
            keys = a.keys()
        for k in keys:
            l = bisect.bisect(self.arr[k], left - 1)
            r = bisect.bisect(self.arr[k], right)
            if r - l >= threshold:
                return k
        return -1