面试题39.md

剑指 Offer 39. 数组中出现次数超过一半的数字

题目描述

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

示例

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2

解法1：哈希表统计法

• 遍历数组 nums ，用 HashMap 统计各数字的数量，最终超过数组长度一半的数字则为众数。此方法时间和空间复杂度均为 O(N)。

• 注：以下代码直接选出了最大次数的数字，因为题目中规定的该数字为一个；

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        if not nums: return None
        nums_dict = {}
        max_count, max_num = 0, nums[0]
        for num in nums:
            if nums_dict.__contains__(num):
                nums_dict[num] += 1
            else: nums_dict.update({num: 1})

            if nums_dict[num] > max_count:
                max_count = nums_dict[num]
                max_num = num
        return max_num

• 也可修改返回对象代码如下：

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        if not nums: return None
        nums_dict = {}
        max_count, max_num = 0, nums[0]
        for num in nums:
            if nums_dict.__contains__(num):
                nums_dict[num] += 1
            else: nums_dict.update({num: 1})

            if nums_dict[num] *2 > len(nums):
                return num                
        return 0

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        target = len(nums) // 2
        hash_map = {}
        for num in nums:
            if num in hash_map:
                hash_map[num] += 1
            else:
                hash_map[num] = 1
            if hash_map[num] > target:
                return num

解法2：数组排序法

• 将所给数组排序，由于众数出现次数大于数组的一半，所以中间元素必为所求数字；
• 时间复杂度：O(nlogn)

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return None
        nums.sort()
        return nums[len(nums) // 2] # /返回浮点数结果  //返回整除结果

解法3：正负票数抵消法 时间O(N)和空间复杂度为 O(1)

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