超级水王问题

一、背景

观看左神的数据结构的讲解，记录一下问题的思路，方便以后复习。

问题描述：给你一个数组，出现次数大于数组长度的一半的元素称之为水王数，怎么能快速找到水王数？
内存限制：时间复杂度O(n)，额外空间复杂度O(1)

二、解决思路

2.1 一般思路

使用一个hashmap记录每次出现的次数，根据出现的次数在进行判断。

优点：直接，很好思考
缺点：不符合题目空间复杂度：O（1）的条件

代码：

这里偷个懒，直接使用collections去做，这个不是重点。

import collections

def test11(num_list: list) -> int:
    count = collections.Counter(num_list).most_common()
    for i in count:
        if i[1] > len(num) >> 1:
            return i[0]
    return -1

2.2 指针法

设置两个指针：
conditional：表示候选的水数
hp：表示水数的个数

规定：
hp为0表示无候选数，否则有候选数

流程：
1. 描述：
    如果hp为0则将当前数设置为候选数
    如果候选数等于当前数则hp加1，否则hp减1
2. 伪代码：
if hp 为 0：
    conditional = flag
    hp = 1
else：
    if conditional == flag：
        hp++
    else:
        hp--

代码：

def verify1(num_list: list) -> int:
    if num_list is None:
        return -1
    # 设置判断的指针
    conditional = 0
    hp = 0
    for i in num_list:
        # hp为0的情况
        if hp == 0:
            conditional = i
            hp = 1
        else:
            # 候选数等于当前值的情况
            if conditional == i:
                hp += 1
            else:
                hp -= 1
    if hp == 0:
        return -1
    # 验证候选数的次数是否大于数组的一半
    times = num_list.count(conditional)
    return conditional if times > len(num_list) >> 1 else -1

三、总结

流程也比较简单，核心思想就是水王数一定可以抵消掉其他的数并有剩余，设置候选数和hp的目的也是为了其他数和水王数做抵消。

四、参考

后期忘记了可以去搜索左神的b站视频。

CSDN的地址