剑指Offer(Python多种思路实现):数组中出现次数超过一半的数字
167 浏览量
2020-12-22
13:45:33
上传
评论
收藏 29KB PDF 举报
剑指剑指Offer(Python多种思路实现多种思路实现):数组中出现次数超过一半的数组中出现次数超过一半的
数字数字
面试39题：
题目：数组中出现次数超过一半的数字
题：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。
由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
解题思路一：根据数组特点找出时间复杂度为解题思路一：根据数组特点找出时间复杂度为O(n)的算法。因为该数字出现次数比其他所有数字出现的次数之和还要多，所的算法。因为该数字出现次数比其他所有数字出现的次数之和还要多，所
有要找的数字肯定是最后一次把次数设为有要找的数字肯定是最后一次把次数设为1时对应的数字。时对应的数字。
class Solution:
def MoreThanHalfNum_Solution(self, numbers):
# write code here
#检查数组是否为无效的输入
if not numbers or len(numbers)<=0:
return 0
res=numbers[0] times=1
for i in range(1,len(numbers)):
if times==0:
res=numbers[i] times=1
elif numbers[i]==res:
times+=1
else:
times-=1
#检查其次数是否大于数组的一半，若不是则返回0
def CheckMoreThanHalf(numbers,number):
length=len(numbers)
times=0
for i in range(length):
if numbers[i]==number:
times+=1
if times*2<=length:
return False
return True
if CheckMoreThanHalf(numbers,res):
return res
return 0
解题思路二：解题思路二：
class Solution:
def MoreThanHalfNum_Solution(self, numbers):
if not numbers or len(numbers)len(numbers) else 0
解题思路三：解题思路三：
def majority_element(nums):
return sorted(nums)[len(nums)//2]
作者：雾行
评论0