2019-08-13 剑指 数组中出现次数超过一半的数字

30min
1.如何循环的写分治有点卡壳
2.针对非法输入进行处理

class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        if not numbers:return 0
        mid=(0+len(numbers)-1)//2
        start,end=0,len(numbers)-1
        p=self.partition(numbers,start,end)
        while p!=mid:
            if p<mid:
                start=p+1 # 这里要进行改变
            else:
                end=p-1
            p=self.partition(numbers,start,end)
        res=numbers[mid]  # 注意非法输入，不存在
        cnt=0
        for n in numbers:
            if n==res:cnt+=1
        if cnt>(len(numbers)/2):return res
        else:return 0



    def partition(self,numbers:List,l:int,r:int)->int:
        pivot=numbers[r]
        small=l-1
        for i in range(l,r):
            if numbers[i]<=pivot:
                small+=1
                if small!=i:numbers[i],numbers[small]=numbers[small],numbers[i]
        small+=1
        numbers[small],numbers[r]=numbers[r],numbers[small]
        return small

转换为迭代写法。可以参考二分查找思路

       if not numbers:return 0
        mid=(0+len(numbers)-1)//2
        self.dfs(numbers,0,len(numbers)-1,mid)

        res=numbers[mid]  # 注意非法输入，不存在
        cnt=0
        for n in numbers:
            if n==res:cnt+=1
        if cnt>(len(numbers)/2):return res
        else:return 0

    def dfs(self,numbers,l,r,mid):
        p=self.partition(numbers,l,r)
        if p<mid:self.dfs(numbers,p+1,r,mid)
        elif p>mid:self.dfs(numbers,l,p-1,mid)

    def partition(self,numbers:List,l:int,r:int)->int:
        pivot=numbers[r]
        small=l-1
        for i in range(l,r):
            if numbers[i]<=pivot:
                small+=1
                if small!=i:numbers[i],numbers[small]=numbers[small],numbers[i]
        small+=1
        numbers[small],numbers[r]=numbers[r],numbers[small]
        return small