数组中出现次数超过一半的数字

2022-08-11
浏览 (412)

数组中出现次数超过一半的数字

题目描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

常规代码

使用一个字典，来记录每个数出现的次数

#  数组中出现次数超过一半的数字
# 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
# -*- coding:utf-8 -*-
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        numsCount = {}
        numLen = len(numbers)
        for num in numbers:
            if num in numsCount:
                numsCount[num] += 1
            else:
                numsCount[num] = 1
            # 找出超过一半的数
            if numsCount[num] > numLen >> 1:
                return num
        return 0

上述代码的空间和时间复杂度都是：O(n)

如果我们要做到，空间复杂度为：O(1)，时间复杂O(n)

升级代码

思路：抵消掉遇到不相同的数字就相互抵消掉，最终剩下的数字就可能是出现次数大于数组长度一半的数字。首先我们来遍历数字，遍历的时候需要记录上次出现的数字是什么，进而判断下次出现的数字是否与现在这个数字相等，如果不相等的话，那么就把两个数字抵消掉，到最后没有抵消掉的数字，就可能是出现的次数大于数组长度的一半。

我们可以考虑在遍历数组的时候保存两个值：一个是数组中的一个数字，另一个是次数；当我们遍历到下一个数字的时候，如果下一个数字和我们之前保存的数字相同，则次数加1，如果下一个数字和我们之前保存的数字不同，则凑数减1.如果次数为0 ，我们需要保存下一次出现的次数，然后把次数设置为1.

class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        #定义变量 上次出现的数字为0
        last = 0
        #上次出现的数字的数量为0 
        lastCount = 0
		#遍历数组中的数字
        for num in numbers:
            #如果说这个数字出现的次数为0了。
            if lastCount == 0:
                #那么就把上次出现的数字，变为需要保存的那个数字。
                last = num
                #并把次数设置为1 次，出现了这一次。
                lastCount = 1
            else:
                #否则就判断，这个数字是不是与上次出现的次数相同，如果相同的话，那么我们这个数字出现的次数就加1.
                if num == last:
                    lastCount += 1
                #如果不同的话，那么我们就让这两个数字抵消掉，那么这个数字出现的次数需要减 1；
                else:
                    lastCount -= 1
		#如果最后遍历完事之后 这个记录数字出现次数的 值为0 的话，那么就说明我们的这个数组里面的数刚好可以两两抵消掉
        if lastCount == 0:
            return 0
        #否则的话，就说明 数组里面 留下了没有抵消掉的数
        else:
            #这种情况是last可能是大于一半的数字
            #这个时候把 记录数字次数的变量 计数 为0 
            lastCount = 0
            #遍历数组中的数
            for num in numbers:
                #如果这个数与我们记录的数相等的话
                if num == last:
                    #让这个计数加1
                    lastCount += 1
			#最后判断一下，这个数的计数次数，是不是大于 我们数组长度的一半，如果是的话，就返回这个数，如果不是就返回0.
            if lastCount > (len(numbers)>> 1):
                return last
        return 0