剑指offer 面试39题

面试39题：

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

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

解题思路：根据数组特点找出时间复杂度为O(n)的算法。因为该数字出现次数比其他所有数字出现的次数之和还要多，所有要找的数字肯定是最后一次把次数设为1时对应的数字。

解题代码一：

# -*- coding:utf-8 -*-

class Solution:

    def MoreThanHalfNum_Solution(self, numbers):

        # write code here

        #检查数组是否为无效的输入

        if not numbers or len(numbers)<=0:

            return 0

        #若存在则该数出现次数比其他所有数字出现次数之和还要多，则要找的数字肯定是最后一次把次数设为1时对应的数字

        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

解题代码二：更简洁。

# -*- coding:utf-8 -*-

class Solution:

    def MoreThanHalfNum_Solution(self, numbers):

        # write code here

        #检查数组是否为无效的输入

        if not numbers or len(numbers)<=0:

            return 0

        #若存在则该数出现次数比其他所有数字出现次数之和还要多，则要找的数字肯定是最后一次把次数设为1时对应的数字

        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

        sum=0

        for j in numbers:

            if j==res:

                sum+=1

        return res if sum*2>len(numbers) else 0