LeetCode.169多数元素

「这是我参与11月更文挑战的第1天，活动详情查看：2021最后一次更文挑战」。

题目描述：

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

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

示例 1:

输入： [3,2,3]
输出： 3
复制代码

示例 2:

输入： [2,2,1,1,1,2,2]
输出： 2
复制代码

进阶：

• 尝试设计时间复杂度为
  $O(n)$

  O(n)、空间复杂度为

  $O(1)$

  O(1) 的算法解决此问题。

思路分析

暴力解法

最容易想到的就是暴力解法了，遍历数组中的每个元素，再遍历一遍其出现的次数，但是该方法的时间复杂度是

O(n2)，超出了我们题目进阶要求的时间复杂度

O(n)，所以pass。

哈希表

其次最容易想到的就是哈希表了，依稀记得做第一题，两数之和的时候就是这个解法。

这里同理，我们依然可以用哈希表来记录每个元素出现的次数，遍历数组，存入哈希表，key为数组中的元素，value为该元素出现的次数。然后我们只需要再遍历一遍这个哈希表就能找到我们的答案。

AC代码

class Solution {
    fun majorityElement(nums: IntArray): Int {
        val map = mutableMapOf<Int,Int>()
        val half = nums.size / 2

        for(num in nums) {
            var n = 0
            if(map.containsKey(num)) {
                n = map[num]!!
            }
            map[num] = n + 1

            if(n + 1 > half) return num
        }
        return -1
    }
} 
复制代码

排序

如果我们有一个元素的个数超过了 n/2 ,那么当我们对数组排序之后，中间的那个数一定是答案。这个不难想象，可以拿笔在纸上比划一下就明白了。

AC代码

class Solution {
    fun majorityElement(nums: IntArray): Int {
        Arrays.sort(nums)
        return nums[nums.size / 2]
    }
}
 
复制代码

总结

这一题虽然是简单题，我给出的两种方法也是比较容易想到的，但是看了题解才发现还有N种解法，包括 随机化， 分治， Boyer-Moore 投票算法。

尴尬，一个都没有听过，好好学习吧。

参考

多数元素 - 多数元素 - 力扣（LeetCode） (leetcode-cn.com)