5.多数元素

题目

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

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

数组中出现次数超过一半的数字被称为众数。

示例 1:

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

示例 2:

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

思路

哈希表

遍历数组nums，用HashMap统计各数字的数量，即可找出众数。 此方法时间和空间复杂度均为O(N)。

排序法

将数组nums排序，数组中心点的元素，一定是众数

摩尔投票法

核心理念是票数正负抵消。此方法的时间和空间复杂度分别为O(N)和O(1)。
为本题最佳解法。

若记 众数 的票数为 +1 ，非众数 的票数为 −1 ，则一定有所有数字的 票数和 >0 。

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

class Solution {
    fun majorityElement(nums: IntArray): Int {
        var vote = 0
        var k = 0
        for (num in nums) {
            if (vote == 0) {
                k = num
            }
            if (num == k) {
                vote ++
            } else {
                vote --
            }
        }
        return k
    }
}

• 下一篇

• 邮箱 ：charon.chui@gmail.com
• Good Luck!