169. 多数元素

题目描述

输入一个长度为 n 的数组 nums。若某个元素出现的次数严格大于 ⌊n/2⌋，就称它为多数元素。

返回这个多数元素。数组非空，且一定存在多数元素。

示例 1

输入：nums = [3,2,3]
输出：3

解释：3 出现 2 次，超过 ⌊3/2⌋ = 1。

示例 2

输入：nums = [2,2,1,1,1,2,2]
输出：2

解释：2 出现 4 次，超过 ⌊7/2⌋ = 3。

数据范围

n == nums.length
1 <= n <= 5 * 10^4
-10^9 <= nums[i] <= 10^9
数组中必有多数元素。

进阶：能否用 O(n) 时间、O(1) 额外空间解决？

解题思路：Boyer-Moore 投票

Boyer-Moore 投票：候选与不同元素抵消，多数元素最终不会被抵消。

为什么正确

扫描前缀中，count 表示候选相对其他元素的未抵消票数。

复杂度分析

时间 O(n)，空间 O(1)。

易错点

算法依赖题目保证多数元素存在；若无此保证，需要第二次计数验证候选。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

from typing import List

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        candidate = None
        count = 0
        for num in nums:
            if count == 0:
                candidate = num
            count += 1 if num == candidate else -1
        return candidate

class Solution {
    public int majorityElement(int[] nums) {
        int candidate = 0;
        int count = 0;
        for (int num : nums) {
            if (count == 0)
                candidate = num;
            count += num == candidate ? 1 : -1;
        }
        return candidate;
    }
}

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate = 0;
        int count = 0;
        for (int num : nums) {
            if (count == 0)
                candidate = num;
            count += num == candidate ? 1 : -1;
        }
        return candidate;
    }
};

func majorityElement(nums []int) int {
    candidate := 0
    count := 0
    for _, num := range nums {
        if count == 0 {
            candidate = num
        }
        if num == candidate {
            count++
        } else {
            count--
        }
    }
    return candidate
}

var majorityElement = function(nums) {
    let candidate = null;
    let count = 0;
    for (const num of nums) {
        if (count === 0)
            candidate = num;
        count += num === candidate ? 1 : -1;
    }
    return candidate;
};

function majorityElement(nums: number[]): number {
    let candidate = 0;
    let count = 0;
    for (const num of nums) {
        if (count === 0)
            candidate = num;
        count += num === candidate ? 1 : -1;
    }
    return candidate;
};

载入编辑器，自己跑一遍 →

其他解法

哈希表计数 O(n) 时间但占 O(n) 空间；排序和分治都是 O(n log n)；投票法同时做到 O(n) 时间和 O(1) 空间。

解法 2：哈希表计数时间 O(n)，空间 O(n)

用哈希表统计每个元素的出现次数。计数时一旦某个元素的次数超过 n/2，就返回它。

最直观，也能推广到“出现次数最多的元素”。需要 O(n) 额外空间。

from typing import List

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        cnt = {}
        for x in nums:
            cnt[x] = cnt.get(x, 0) + 1
            if cnt[x] * 2 > len(nums):
                return x
        return -1

class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> cnt = new HashMap<>();
        int n = nums.length;
        for (int x : nums) {
            int c = cnt.merge(x, 1, Integer::sum);
            if (c * 2 > n) return x;
        }
        return -1;
    }
}

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> cnt;
        int n = nums.size();
        for (int x : nums) {
            if (++cnt[x] * 2 > n) return x;
        }
        return -1;
    }
};

func majorityElement(nums []int) int {
	cnt := map[int]int{}
	for _, x := range nums {
		cnt[x]++
		if cnt[x]*2 > len(nums) {
			return x
		}
	}
	return -1
}

var majorityElement = function(nums) {
    const cnt = new Map();
    for (const x of nums) {
        const c = (cnt.get(x) || 0) + 1;
        cnt.set(x, c);
        if (c * 2 > nums.length) return x;
    }
    return -1;
};

function majorityElement(nums: number[]): number {
    const cnt = new Map<number, number>();
    for (const x of nums) {
        const c = (cnt.get(x) ?? 0) + 1;
        cnt.set(x, c);
        if (c * 2 > nums.length) return x;
    }
    return -1;
};

解法 3：排序取中位时间 O(n log n)，空间 O(log n)

把数组排序。多数元素出现超过 n/2 次，排序后它占据的连续区间一定覆盖下标 n/2。直接返回 nums[n/2]。

只有两行代码，关键是理解“中位数必是多数元素”。时间多一个 log n，并且会打乱输入顺序。

from typing import List

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        nums.sort()
        return nums[len(nums) // 2]

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

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        return nums[nums.size() / 2];
    }
};

func majorityElement(nums []int) int {
	sort.Ints(nums)
	return nums[len(nums)/2]
}

var majorityElement = function(nums) {
    nums.sort((a, b) => a - b);
    return nums[nums.length >> 1];
};

function majorityElement(nums: number[]): number {
    nums.sort((a, b) => a - b);
    return nums[nums.length >> 1];
};

解法 4：分治时间 O(n log n)，空间 O(log n)

把区间对半分开，递归求左右两半各自的多数元素。若两边结果相同就直接返回。否则在整个区间内分别统计两个候选的次数，返回次数更多的那个。

依据是全局多数元素至少是某一半的多数元素，是分治思想的好例子。时间和空间都不如投票法。

from typing import List

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        def count(x, lo, hi):
            return sum(1 for i in range(lo, hi + 1) if nums[i] == x)

        def solve(lo, hi):
            if lo == hi:
                return nums[lo]
            mid = (lo + hi) // 2
            left = solve(lo, mid)
            right = solve(mid + 1, hi)
            if left == right:
                return left
            return left if count(left, lo, hi) > count(right, lo, hi) else right

        return solve(0, len(nums) - 1)

class Solution {
    private int count(int[] nums, int x, int lo, int hi) {
        int c = 0;
        for (int i = lo; i <= hi; i++) if (nums[i] == x) c++;
        return c;
    }

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

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

class Solution {
    int count(vector<int>& nums, int x, int lo, int hi) {
        int c = 0;
        for (int i = lo; i <= hi; i++) if (nums[i] == x) c++;
        return c;
    }

    int solve(vector<int>& nums, int lo, int hi) {
        if (lo == hi) return nums[lo];
        int mid = (lo + hi) / 2;
        int left = solve(nums, lo, mid), right = solve(nums, mid + 1, hi);
        if (left == right) return left;
        return count(nums, left, lo, hi) > count(nums, right, lo, hi) ? left : right;
    }
public:
    int majorityElement(vector<int>& nums) {
        return solve(nums, 0, nums.size() - 1);
    }
};

func majorityElement(nums []int) int {
	count := func(x, lo, hi int) int {
		c := 0
		for i := lo; i <= hi; i++ {
			if nums[i] == x {
				c++
			}
		}
		return c
	}
	var solve func(lo, hi int) int
	solve = func(lo, hi int) int {
		if lo == hi {
			return nums[lo]
		}
		mid := (lo + hi) / 2
		left, right := solve(lo, mid), solve(mid+1, hi)
		if left == right {
			return left
		}
		if count(left, lo, hi) > count(right, lo, hi) {
			return left
		}
		return right
	}
	return solve(0, len(nums)-1)
}

var majorityElement = function(nums) {
    const count = (x, lo, hi) => {
        let c = 0;
        for (let i = lo; i <= hi; i++) if (nums[i] === x) c++;
        return c;
    };
    const solve = (lo, hi) => {
        if (lo === hi) return nums[lo];
        const mid = (lo + hi) >> 1;
        const left = solve(lo, mid), right = solve(mid + 1, hi);
        if (left === right) return left;
        return count(left, lo, hi) > count(right, lo, hi) ? left : right;
    };
    return solve(0, nums.length - 1);
};

function majorityElement(nums: number[]): number {
    const count = (x: number, lo: number, hi: number): number => {
        let c = 0;
        for (let i = lo; i <= hi; i++) if (nums[i] === x) c++;
        return c;
    };
    const solve = (lo: number, hi: number): number => {
        if (lo === hi) return nums[lo];
        const mid = (lo + hi) >> 1;
        const left = solve(lo, mid), right = solve(mid + 1, hi);
        if (left === right) return left;
        return count(left, lo, hi) > count(right, lo, hi) ? left : right;
    };
    return solve(0, nums.length - 1);
};

技巧专题的其他题目

查看技巧全部题目 →