Leetcode刷题：剑指offer【面试题39 数组中出现次数超过一半的数字】

【面试题39 数组中出现次数超过一半的数字】

难度： 简单

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。你可以假设数组是非空的，并且给定的数组总是存在多数元素。

Leetcode题目对应位置： 面试题39：数组中出现次数超过一半的数字

思路 1：使用哈希表，存储遇到过的数字出现的次数，一旦找到出现次数大于数组长度的一般的数，直接返回。

时间复杂度：O(n)
空间复杂度：O(n)

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        n, res = len(nums), {}
        for i in range(n):
            if nums[i] not in res:
                res[nums[i]] = 1
            else:
                res[nums[i]] += 1
            if res[nums[i]] >= (n + 1) / 2:
                return nums[i]

思路 2：对数组进行排序，取数组最中间的数。因为某数个数大于数组长度的一半，那么排序后它势必会在数组的中间位置。

时间复杂度：O(nlog2n)
空间复杂度：O(1)

思路 3：摩尔投票法。遍历数组，用 vote 变量记录当前票数。

• vote 若为 0，则将当前遍历到的位置元素 “当作” 众数，继续向后遍历，若和当前的众数相等，则 vote +1，否则 vote -1
• 循环遍历到数组末尾，当前假设的众数就是真正的众数。

每一次 vote = 0 时，都将当前元素作为众数，可以保证最后找到的数的确是众数，因为：

• 假如 当前元素 = 真正的众数，那么其后面抵消的就是一个众数和一个非众数，后面留下的数字仍能保证众数占一半；
• 假如 当前元素 ≠ 真正的众数，那么抵消的就是俩非众数，后面留下的数字大于或等于一半都是众数。

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        n, vote = len(nums), 0
        for i in range(n):
            if vote == 0:
                cur = nums[i]  # 当前众数
                vote += 1
            else:
                if nums[i] != cur: vote -= 1
                else: vote += 1
        return cur

大佬的简洁代码：

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

代码来源：mian-shi-ti-39-shu-zu-zhong-chu-xian-ci-shu-chao-3

最后

以上就是美好小鸭子为你收集整理的Leetcode刷题：剑指offer【面试题39 数组中出现次数超过一半的数字】的全部内容，希望文章能够帮你解决Leetcode刷题：剑指offer【面试题39 数组中出现次数超过一半的数字】所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。