超级水王问题

问题描述
假设有一个数组，如果数组中的某一项出现的次数大于数组长度的一半，则这一项就是水王？

可能是因为帖子评论区一半以上的评论都出自于某个用户，表示这个用户一直在灌水吧

问题分析

• 要求时间复杂度是O(n)
• 空间复杂度控制在O(1)
  如果遍历时使用map统计每一项出现的次数，最坏的空间复杂度很显然是O(n)

解题思路
根据题目，如果水王存在的话，水王的个数是大于数组长度的一半，那么如果把数组中任意两个不相同的项同时消除的话，很显然水王不会被全部消除(但是反过来，是不一定成立的，大家可以想一下为什么？)。
现在问题变成怎样消除数组中一对不同的项，很多人可能想到了使用栈，依次遍历数组，如果栈为空，则进行入栈操作，如果站不为空，判断当前遍历的值与栈底的值是不是想等，如果相等则进行入栈操作，如果不想等则进行出栈操作，最后判断栈中的值，大家可以想一想，这样做对吗？
很显然上面使用栈来操作消除数组中一对不同的项的操作违反了空间复杂度为O(1)的原则，那么该怎样消除呢？
现在提出一个血量的概念，这个血量就可以看作剩余水王的数量，初始将血量设置为0，水王设置为None，遍历数组，判断血量是否为0？

• 如果血量为0，则设置水王为当前遍历出的值
• 如果血量不为空，则判断当前遍历的值和水王的值是否相等
  • 如果想等，则血量加1
  • 如果不想等，则血量减1
• 最后判断判断血量是否为0，如果为0，则肯定不存在水王，如果不为0，那么则需要再次判断水王的值在数组中出现的次数(为什么？[1, 2, 3, 4, 5])。

这样做就可以保证空间复杂度为O(1)，代码实现如下：

def super_water_king(arr):
    """ 超级水王问题

    desc: 一个数组中单个项出现的次数大于当前数组长度的一半
    idea: 遍历数组，相邻(当前遍历数字与靶子值相比)两个数字相同则靶子数(即血量)+1，如果相邻的两个数字不相同则靶子数(即血量)-1
          如果血量为0，表示靶子没有了，把当前被遍历的数字设置为靶子，同时血量设置为1，这样使用血量的方式就可以控制靶子的变化或者靶子数的增减
    """

    if not arr:
        return False

    # 先设定当前靶子为空，血量为0
    # 如果血量为0时，表示当前靶子为空，此时需要添加靶子
    # 如果血量不为0：
    #   1、如果当前遍历的值与靶子相同，血量加1
    #   2、如果当前遍历的值与靶子不相同，血量减1
    # 如果遍历完成后，血量为0， 则肯定不存在超级水王数
    # 如果遍历完成后，血量不为0， 要再一次遍历全部数组，计算当前靶子数字出现的次数
    target = None
    curr_hp = 0

    for n in arr:
        if curr_hp == 0:
            target = n
            curr_hp = 1
        elif n != target:
            curr_hp -= 1
        else:
            curr_hp += 1

    if curr_hp == 0:
        return False

    count = 0
    for i in arr:
        if i == target:
            count += 1

    if count > len(arr) >> 1:
        return True

    return False


# Test
for _ in range(10):
    arrs = [random.randint(10, 12) for i in range(10)]
    print(arrs)
    print(super_water_king(arrs))

问题的思考
1、数组中消除同类或者异类的操作是不是可以归结到靶子(水王)和血量上来呢？
2、选举中获取一般票数以上的人当选的问题是否也可以归结为水王问题?
3、消除过后如果剩余的血量为0，则不存在水王，但是如果血量不为0，千万别以为水王就存在，这是不成立的。