本文共 2286 字，大约阅读时间需要 7 分钟。

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

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

# 方法1;常见方法,使用字典的方法def MoreThanHalfNum_Solution(numbers):    len1 = len(numbers)    if len1==0:        return 0    a={}    for i in numbers:        if not a.get(i):            a[i]=1        else:            a[i]+=1    a=sorted(a.items(),key=lambda x:x[1])[-1]  # 选出出现次数 最多的那一组    print('aaaaa',a)    if a[1]>len1//2:        return int(a[0])    else:        return 0  if __name__ == '__main__':    try:        while True:            arr = [int(i) for i in input().split()]            print(MoreThanHalfNum_Solution(arr))    except:        pass

# 方法2:时间复杂度为O(NlogN)# 数组排序后，如果符合条件的数存在，则一定是数组中间那个数。这种方法虽然容易理解，但由于涉及到快排sort，其时间复杂度为O(NlogN)并非最优def MoreThanHalfNum_Solution(numbers):    len1 = len(numbers)    if len1==0:        return 0    numbers.sort() # 排序    middle = numbers[len1 // 2] #取排序后的中位数     # 判断middle是否符合条件，即出现次数大于数组长度的一半    counts = 0    for j in range(len1):        if numbers[j] == middle:            counts += 1    if counts>len1//2: # python3整除为//，python2为/        return middle    else:        return 0  if __name__ == '__main__':    try:        while True:            arr = [int(i) for i in input().split()]            print(MoreThanHalfNum_Solution(arr))    except:        pass

# 方法3：时间复杂度为O(N)# 如果有符合条件的数字，则它出现的次数比其他所有数字出现的次数和还要多。def MoreThanHalfNum_Solution(numbers):    len1 = len(numbers)    if len1==0:        return 0    # 遍历每个元素，并记录次数；若与前一个元素相同，则次数加1，否则次数减1    target = numbers[0] # 初始值    count = 1 # 次数    for i in range(1,len1):        if count == 0:            # 更新result的值为当前元素，并置次数为1            target = numbers[i]            count = 1        elif numbers[i] == target:            count += 1 # 相同则加1        elif numbers[i] != target:            count -= 1 # # 不同则加1    # 判断target是否符合条件，即出现次数大于数组长度的一半    if count > 0:        count = 0        for j in range(len1):            if numbers[j] == target:                count += 1        if count>len1//2: # python3整除为//，python2为/            return target        else:            return 0    else:        return 0  if __name__ == '__main__':    try:        while True:            arr = [int(i) for i in input().split()]            print(MoreThanHalfNum_Solution(arr))    except:        pass

转载地址：https://blog.csdn.net/zz2230633069/article/details/102520311 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！