从字符串数组中找出出现次数超当前数组长度一半的元素，要求时间复杂

代码如下

    public static String getMoreThanHalfFrom(String[] strs) {
        if (strs == null || strs.length < 1) {
            throw new IllegalArgumentException("参数不合法");
        }

        // 数组长度
        int length = strs.length;

        // 数组长度一半
        int half = (int) Math.ceil(length / 2.0);

        int mapCap = (int) (length / 0.75) + 1;

        HashMap<String, Integer> frequentMap = new HashMap<>(mapCap);

        // 从字符串数组中找出出现次数超当前数组长度一半的元素，要求时间复杂度不得大于O(n)
        for (int i = 0; i < strs.length; i++) {
            String str = strs[i];
            Integer times = frequentMap.get(str);
            if (times == null) {
                times = 1;
            } else {
                times++;
            }
            frequentMap.put(str,times);
            if (times >= half)
                return str;
        }
        throw new RuntimeException("不存在出现次数超当前数组长度一半的元素");
    }

更优解

    // 从字符串数组中找出出现次数超当前数组长度一半的元素，要求时间复杂度不得大于O(n)，并不使用Map
    public static String getMoreThanHalfFromPro(String[] strs) {
        if (strs == null || strs.length < 1) {
            throw new IllegalArgumentException("参数不合法");
        }
        int times = 0;
        String objStr = strs[0];
        // 核心原理，去掉数组中两个不一样的元素，出现次数超过一半的元素依旧存在且不受影响
        for (int i = 0; i < strs.length; i++) {
            String str = strs[i];
            if (str == objStr) {
                times++;
            } else {
                times--;
            }
            if (times == 0) {
                objStr = str;
                times = 1;
            }
        }
        // 认证，略...
        return objStr; // 要求传入的数组必须存在这样一个元素
    }