超级水王问题

0. 学习资料

1. 什么是水王数

  • 如果有某个数,它在数组中出现的次数大于整个数组长度的一半以上,这个数就是水王
  • 比如数组[1,2,3,3,4,3,5,3,3],3是水王数

2. 常规解法

  • 把数组遍历一遍,用一个哈希表存放每个数出现的次数,次数大于数组长度一半的,即为水王数

image.png

  • 代码实现
    • 时间复杂度O(N)
    • 空间复杂度O(N)
import java.util.HashMap;
import java.util.Map;

public class Code01_SuperWaterKing {
    
    public static void main(String[] args) {
        int[] arr = {2, 5, 2, 7, 2, 1, 2};
        int length = arr.length;
        System.out.println("数组长度是: " + length + "\n"
                + "水王数是: " + verify(arr)
        );
    }

    public static int verify(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        // 创建一个哈希表存放数字出现的频次
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : arr) {
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }
        int length = arr.length;
        // 数字的频次大于数组长度一半时,即得到水王数
        for (Map.Entry<Integer, Integer> record : map.entrySet()) {
            if (record.getValue() > (length >> 1)) {
                return record.getKey();
            }
        }
        return -1;
    }
}
  • 水王问题的限制,时间复杂度O(N)空间复杂度O(1),因此,常规解法不满足解题要求

3. 真正要实现的解法

  • 思路是:一次删除两个不相同的数,最后如果有水王数的话,它会剩下来,反之不成立
    • 把水王数想象成大BOSS,其它的数都与之为敌,遇到一个就相互抵消
    • 考虑到其它数之间也是会互相抵消,因此,剩下来的也不一定是水王数,比如,数组[1,2,3,4,5];因此,剩下来的数,还要再遍历一次,判断它的频次是否大于数组长度的一半

image.png

  • 代码实现,定义两个变量,候选血量,当血量==0时,说明无候选,当血量>0时,说明有候选
    • 如果无候选,当前数立为候选血量=1
    • 如果有候选
      • 当前数==候选时,血量+1
      • 当前数!=候选时,血量-1

image.png

public class Code01_SuperWaterKing {

    public static void main(String[] args) {
        int[] arr = {1, 5, 2, 7, 2, 1, 2};
        int length = arr.length;
        System.out.println("数组长度是: " + length + "\n"
                + "水王数是: " + waterKing(arr)
        );
    }

    public static int waterKing(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        int candidate = 0;
        int restHP = 0;
        for (int cur : arr) {
            if (restHP == 0) {  // 如果没有获选
                candidate = cur;
                restHP = 1;
            } else if (cur == candidate) {  // 如果有候选,且当前数和候选一样,血量+1
                restHP++;
            } else {  // 如果有候选,且当前数和候选不一样,血量-1
                restHP--;
            }
        }
        if (restHP == 0) {
            return -1;
        }
        // 如果有候选留下来,再遍历一遍,得到候选真正出现的次数
        int count = 0;
        for (int cur : arr) {
            if (cur == candidate) {
                count++;
            }
        }
        int length = arr.length;
        return count > (length >> 1) ? candidate : -1;
    }
}