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

destiny_python

于 2017-07-26 21:27:50 发布

阅读量295

点赞数

分类专栏： python 剑指offer 文章标签： python

本文链接：https://blog.csdn.net/destiny_python/article/details/76165818

版权

python 同时被 2 个专栏收录

19 篇文章

订阅专栏

剑指offer

10 篇文章

订阅专栏

本文介绍了一种寻找数组中出现次数超过一半的众数的算法。该算法通过遍历数组两次来实现：第一次遍历确定可能的众数，第二次遍历验证这个数是否真正超过了数组长度的一半。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

# -*- coding:utf-8 -*-
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here 
        if (numbers == None or len(numbers) <= 0):
            return 0
        result = numbers[0]
        times = 1
        length = len(numbers)
        for i in range(1,length):
            if times == 0:
                result = numbers[i]
                times = 1
            elif numbers[i] == result:
                times += 1
            else:
                times -= 1
        if(self.CheckMoreThanHalf(numbers, result)):
            result = 0
        return result
                
    #判断数组中出现result的次数是否超过数组长度的一半
    def CheckMoreThanHalf(self, numbers, result):
        times = 0
        length = len(numbers)
        for i in range(length):
            if numbers[i] == result:
                times += 1
        if (times * 2 <= length):
            return True
        return False