leetcode：1157. 子数组中占绝大多数的元素【暴力遍历 + 随机算法相信概率】

题目截图

题目分析

• 一个很暴力的思路就是把每个num出现的idx记录起来，然后按出现的频率排序优化
• 每次query，遍历每个元素和频率，频率如果已经比threhold小就没有看的必要，直接break
• 如果比它大，我们通过d获得其ids序列，左右二分其left和right得到两个下标l和r
• 如果r - l >= threhold说明中间夹着大于threhold个，就满足了
• 但是这个几乎超时
• 特别地，我们可以考虑随机算法
• 由于一个区间要么存在一个答案，要么不存在答案
• 也就是由于2 * threhold > len([l, r])
• 这样的话如果存在，抽不到一个符合的num的概率小于0.5
• 如果超过k次都抽不到且又存在答案的话，这个概率是小于0.5 ^ k
• 所以不妨k = 30，如果超过30次扔找不到答案，我们就认为它没有答案；答案在arr[l:r + 1]中随机抽取

暴力二分

class MajorityChecker:
    # threshold过半最多只有一个
    def __init__(self, arr: List[int]):
        # 记录每个值出现的index
        self.d = defaultdict(list)
        for i, v in enumerate(arr):
            self.d[v].append(i)
        # 出现频率的统计(从大到小)
        self.freq = sorted([(len(ids), value) for value, ids in self.d.items()], reverse = True)


    def query(self, left: int, right: int, threshold: int) -> int:
        for f, v in self.freq:
            if f < threshold: break
            ids = self.d[v]
            l = bisect_left(ids, left)
            r = bisect_right(ids, right)
            if r - l >= threshold:
                return v
        return -1



# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)
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

随机二分

class MajorityChecker:
    # threshold过半最多只有一个
    def __init__(self, arr: List[int]):
        # 记录每个值出现的index
        self.arr = arr
        self.d = defaultdict(list)
        for i, v in enumerate(arr):
            self.d[v].append(i)
        # 出现频率的统计(从大到小)
        # self.freq = sorted([(len(ids), value) for value, ids in self.d.items()], reverse = True)


    def query(self, left: int, right: int, threshold: int) -> int:
        # 随机从[l, r]抽一个数
        # 如果存在答案，那么抽不到答案的概率小于0.5
        # 多次都抽不到答案，认为没有答案，返回-1
        Round = 30
        for _ in range(Round):
            choice = self.arr[random.randint(left, right)]
            l = bisect_left(self.d[choice], left)
            r = bisect_right(self.d[choice], right)
            if r - l >= threshold:
                return choice
        return -1



# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)
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

总结

• 使用随机算法优化
• 通过概率论可知，随机算法确实是概率正确的