题目链接

英文链接：https://leetcode.com/problems/majority-element/

中文链接：https://leetcode-cn.com/problems/majority-element/

题目详述

给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在众数。

示例 1:

1 2	输入: [3,2,3] 输出: 3

示例 2:

1 2	输入: [2,2,1,1,1,2,2] 输出: 2

题目详解

解决本问题的方法有很多，可以排序，然后取中位数。时间复杂度为 O(nlogn)。

public class LeetCode_00169 {

    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}

也可以采用分治算法。时间复杂度为 O(nlogn)。

将问题分成两个子问题。
如果两个子问题的众数相等，说明这个众数也是原问题的众数。
如果不等，则两者均有可能，分别在原问题中统计两者的个数，取较大者。

public class LeetCode_00169 {

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

    private int majorityElement(int[] nums, int lo, int hi) {
        if (lo == hi) {
            return nums[lo];
        }
        int mid = lo + (hi - lo) / 2;
        int left = majorityElement(nums, lo, mid);
        int right = majorityElement(nums, mid + 1, hi);
        if (left == right) {
            return left;
        }
        return countRange(left, nums, lo, hi) > countRange(right, nums, lo, hi) ? left : right;
    }

    private int countRange(int num, int[] nums, int lo, int hi) {
        int cnt = 0;
        for (int i = lo; i <= hi; ++i) {
            if (nums[i] == num) {
                ++cnt;
            }
        }
        return cnt;
    }
}

找到超过一半元素更好的方式是采用摩尔投票算法。时间复杂度为 O(n)。

用 candidate 表示候选元素，cnt 表示票数。
若票数为 0，则选取当前元素为新的候选元素。
若当前元素等于候选元素，则票数加一；否则减一。
遍历结束后的候选元素就是众数（由于题目保证给定的数组总是存在众数，所以不需要额外判断，否则需要判断是否存在众数）。

public class LeetCode_00169 {

    // 摩尔投票算法
    public int majorityElement(int[] nums) {
        int candidate = nums[0];
        int cnt = 0;
        for (int num : nums) {
            if (cnt == 0) {
                candidate = num;
            }
            cnt += (num == candidate) ? 1 : -1;
        }
        return candidate;
    }
}