image.png

方法一：排序法
分析：無論眾數(shù)是數(shù)組中最大或是最小北启，眾數(shù)都會在數(shù)組中心出現(xiàn)卜朗，即（nums.length/2）的位置始終是眾數(shù)。

public int majorityElement(int[] nums) {
        //排序法：眾數(shù)始終出現(xiàn)在中心
        Arrays.sort(nums);
        return nums[nums.length/2];
    }

時間復(fù)雜度：即排序的時間復(fù)雜度O(nlogn)
空間復(fù)雜度：排序的空間復(fù)雜度O(logn)

方法二：哈希表法
思路：1）將數(shù)組中的數(shù)以及它的出現(xiàn)次數(shù)存放到哈希表中咕村，
2）遍歷哈希映射中的所有鍵值對场钉，返回值最大的鍵

public static int majorityElement(int[] nums) {
        //哈希表法
        Map<Integer,Integer> counts = new HashMap<Integer,Integer>();
        for(int num : nums){
            if(!counts.containsKey(num)){
                counts.put(num,1);
            }else {
                counts.put(num,counts.get(num)+1);
            }
        }

        Map.Entry<Integer,Integer> majorityEntry = null;
        for (Map.Entry<Integer,Integer> entry : counts.entrySet()){
            if(majorityEntry == null || entry.getValue() > majorityEntry.getValue()){
                majorityEntry = entry;
            }
        }

        return  majorityEntry.getKey();
    }

時間復(fù)雜度O(n)
空間復(fù)雜度O(n)

方法三:分治法
思路：長度為 1 的子數(shù)組中唯一的數(shù)顯然是眾數(shù)，直接返回即可懈涛。如果回溯后某區(qū)間的長度大于 1惹悄，我們必須將左右子區(qū)間的值合并。如果它們的眾數(shù)相同肩钠，那么顯然這一段區(qū)間的眾數(shù)是它們相同的值泣港。否則，我們需要比較兩個眾數(shù)在整個區(qū)間內(nèi)出現(xiàn)的次數(shù)來決定該區(qū)間的眾數(shù)价匠。

//分治法
    private int countInRange(int[] nums, int num, int lo, int hi) {
        int count = 0;
        for (int i = lo; i <= hi; i++) {
            if (nums[i] == num) {
                count++;
            }
        }
        return count;
    }

    private int majorityElementRec(int[] nums, int lo, int hi) {
        if (lo == hi) {
            return nums[lo];
        }
        
        int mid = (hi - lo) / 2 + lo;
        int left = majorityElementRec(nums, lo, mid);
        int right = majorityElementRec(nums, mid + 1, hi);
        
        if (left == right) {
            return left;
        }
        
        int leftCount = countInRange(nums, left, lo, hi);
        int rightCount = countInRange(nums, right, lo, hi);

        return leftCount > rightCount ? left : right;
    }

    public int majorityElement(int[] nums) {
        return majorityElementRec(nums, 0, nums.length - 1);
    }