Skip to content

Latest commit

 

History

History
86 lines (72 loc) · 4.03 KB

File metadata and controls

86 lines (72 loc) · 4.03 KB

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

题目描述

数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为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