image.png

方法一：排序法
分析：无论众数是数组中最大或是最小，众数都会在数组中心出现，即（nums.length/2）的位置始终是众数。

public int majorityElement(int[] nums) {
        //排序法：众数始终出现在中心
        Arrays.sort(nums);
        return nums[nums.length/2];
    }

时间复杂度：即排序的时间复杂度O(nlogn)
空间复杂度：排序的空间复杂度O(logn)

方法二：哈希表法
思路：1）将数组中的数以及它的出现次数存放到哈希表中，
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();
    }

时间复杂度O(n)
空间复杂度O(n)

方法三:分治法
思路：长度为 1 的子数组中唯一的数显然是众数，直接返回即可。如果回溯后某区间的长度大于 1，我们必须将左右子区间的值合并。如果它们的众数相同，那么显然这一段区间的众数是它们相同的值。否则，我们需要比较两个众数在整个区间内出现的次数来决定该区间的众数。

//分治法
    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);
    }