多数元素

发表于 分类于 阅读次数：

多数元素（难度：简单）

1

注意：这样的元素只存在一个，因为出现次数大于n/2，若存在两个，则数组长度会超过n。

方法一：

在Python中，先用set()找出所有出现的元素，再使用count()判断出现次数大于n/2的。

1
2
3
4
5
6
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        set1 = set(nums)
        for s in set1:
            if nums.count(s) > len(nums)//2:
                return s
2

方法二：

先排序，再返回位于n/2位置的元素。

复杂度

时间复杂度：O(nlogn)。用 Python 和 Java 将数组排序开销都为 O(nlogn)，它占据了运行的主要时间。

空间复杂度：O(1)或O(n)。就地排序或使用线性空间将 nums 数组拷贝，然后再排序。

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

方法三：Boyer-Moore 投票算法

从第一个数开始count=1，遇到相同的就加1，遇到不同的就减1，减到0就重新换个数开始计数，最后总能找到最多的那个。

复杂度

时间复杂度：O(n)。严格执行了 n 次循环。

空间复杂度：O(1)。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = 0
        candidate = nums[0]

        for num in nums:
            if count == 0:
                candidate = num
            if num==candidate:
                count += 1
            else:
                count -= 1
        
        return candidate
4