题解 | #数组中出现次数超过一半的数字#

• 第一种方法，数组排序+各元素计数
• 第二种方法：HashMap统计次数

import java.util.*;
public class Solution {
    // 1.第一种方法，数组排序+各元素计数
    public int MoreThanHalfNum_Solution(int [] array) {
        if (array.length <= 1) {
            return array[array.length - 1];
        }
        // 先进行排序
        Arrays.sort(array);
        int count = 0;
        int half = array.length / 2;
        // 遍历这个有序数组
        for (int i = 0; i < array.length; i++) {
            if (i == 0) { // 第一个元素count置为1
                count++;
            } else {
                // 当前元素与前一个元素相同，则count++
                if (array[i] == array[i - 1]) {
                    count++;
                    // 当前这个元素个数超过了半数，则return这个元素
                    if (count > half) {
                        return array[i];
                    }
                } else {
                    // 如果当前元素与前一个元素不同，则count置为1重新来计数
                    count = 1;
                }
            }

        }
        return -1;
    }

    /*
    // 2.第二种方法：HashMap统计次数
    public int MoreThanHalfNum_Solution(int [] array) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < array.length; i++) {
            map.put(array[i], map.getOrDefault(array[i], 0) + 1);
        }
        for(Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if(entry.getValue() > (array.length / 2)) {
                return entry.getKey();
            }
        }
        return -1;
    }
    */
}