Skip to content

169. Majority Element

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example 1:

Input: nums = [3,2,3]
Output: 3

Example 2:

Input: nums = [2,2,1,1,1,2,2]
Output: 2

Solution:

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

// TC: O(nlogn)
// SC: O(n) or O(1)

Boyer-Moore Voting Algorithm

class Solution {
    public int majorityElement(int[] nums) {
        int candidate = nums[0]; // 3
        int count = 1;
        for (int i = 1; i < nums.length; i++){
            if (count == 0){
                count++;
                candidate = nums[i];
            }else if (candidate == nums[i]){
                count++;
            }else{
                count--;
            }
        }
        return candidate;
    }
}
//  Boyer-Moore Voting Algorithm

// TC: O(n)
// SC: O(1)

class Solution {
    public int majorityElement(int[] nums) {
        int majCount = 0;
        int majNum = 0;
        int n = nums.length; 

        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++){
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);

            if (majCount <= map.get(nums[i])){
                majCount = map.get(nums[i]);
                majNum = nums[i];
            }

            if (majCount > n/2){
                return majNum;
            }
        }
        return -1;
    }
}

题意：计算 nums 的严格众数。严格众数的出现次数，比其余所有元素的出现次数加起来还多。

题目保证 nums 一定存在严格众数。

尝试设计一个 O(n) 一次遍历，同时只用到 O(1) 额外空间的算法。

想象一众武林高手比武，谁会笑到最后？

我用「擂台赛」打比方：

擂主登场：nums[0] 成为初始擂主，生命值为 1。 挑战者出现：遍历后续元素，作为挑战者。 比武：如果挑战者与擂主属于同一门派（值相同），那么擂主生命值加 1，否则擂主生命值减 1。 擂主更迭：如果比武后，擂主生命值降为 0（同归于尽），那么下一个挑战者成为新的擂主，生命值为 1。 最后在擂台上的那人，便是武林盟主（严格众数）。 为什么这样做是对的？

设出现次数最多的元素的出现次数为 a，其余元素的出现次数之和为 b=n−a。题目保证 a>b。

证明：上述过程中，每次擂主的生命值降为 0 时，相当于开了一个新的擂台赛，在 nums[i] 和 nums[i+1] 之间切一刀。这会把 nums 分成若干段。依次考察这些段：

对于除了最后一段的每一段，设严格众数在其中出现了 x 次，其余元素的出现次数之和为 y，必然有 x≤y。这可以用反证法证明，如果 x>y，那么严格众数血多，不可能被其余元素同归于尽，严格众数的生命值在这段结束时必然大于 0，矛盾。由此可得 a−x>b−y，意思是，把 a 减去 x，b 减去 y，所得到的 a′和 b′仍然满足 a′ >b'. 依此类推，每一段结束时，在剩余元素（未遍历到的元素）中，设出现次数最多的元素的出现次数为 a′，其余元素的出现次数之和为 b′，那么 a′> b′始终成立。 对于最后一段，由于 a′>b′, 严格众数血多，不可能被其余元素同归于尽，严格众数的生命值最终必然大于 0，所以最后在擂台上的是严格众数。

复杂度分析

  • 时间复杂度：O(n)，其中 n 是 nums 的长度。
  • 空间复杂度：O(1)。
class Solution {
    public int majorityElement(int[] nums) {
        int result = 0;
        int hp = 0;
        for (int x : nums){
            if (hp == 0){ // x是初始擂主, 生命值为1
                result = x;
                hp = 1;
            }else{ // 比武, 同门加血,否则扣血   
                if (x == result){
                    hp = hp + 1;    
                }else{
                    hp = hp - 1;
                }
            }
        }   

        return result;
    }
}

// TC: O(n)
// SC: O(1)