剑指offer 28. 数组中出现次数超过一半的数字

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

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

思路
思路1：
遍历数组，用字典dict存储数组中某个数字出现的次数，当这个数字出现的次数大于数组长度的一半时，返回这个数字。时间复杂度为O(n)，空间复杂度O(1)~O(n)，开辟了字典dict，最优为1最差为n。
思路2：
对数组进行排序，如果数组中有一个数字出现的次数超过数组长度的一半，那么这个数字一定在数组的中间。python的sort()函数的时间复杂度最差是O(nlogn)<O(n)，所以这种方法的时间复杂度是O(nlogn)，空间复杂度O(1)。
Timsort原理介绍
思路3：
数组中有一个数字出现的次数超过数组长度的一半，也就是说它出现的次数比其他所有数字出现次数的和还要多。因此我们可以考虑在遍历数组的时候保存两个值：一个是数组的一个数字，一个是次数。当我们遍历到下一个数字的时候，如果下一个数字和我们之前保存的数字相同，则次数加1；如果下一个数字和我们之前保存的数字不同，则次数减1。如果次数为零，我们需要保存下一个数字，并把次数设为1。由于我们要找的数字出现的次数比其他所有数字出现的次数之和还要多，那么要找的数字肯定是最后一次把次数设为1时对应的数字。时间复杂度是O(n)，空间复杂度O(1)。

代码实现
思路1：遍历数组，用字典dict存储次数。时间复杂度为O(n)，空间复杂度O(1)~O(n)

# -*- coding:utf-8 -*-
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        length = len(numbers)
        if (length == 0):
            return 0
        elif(length == 1):
            return numbers[0]
        else:
            dict = {}
            for i in range(length):
                if(numbers[i] in dict):
                    dict[numbers[i]] += 1
                    if(dict[numbers[i]] > length/2):
                        return numbers[i]
                else:
                    dict[numbers[i]] = 1
            return 0

思路2：先排序，再判断中间的那个数。时间复杂度是O(n)，空间复杂度O(1)

# -*- coding:utf-8 -*-
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        length = len(numbers)
        if (length == 0):
            return 0
        elif(length == 1):
            return numbers[0]
        else:
            numbers.sort()
            num = numbers[int(length/2)]
            if(numbers.count(num) > len(numbers)/2):
                return num
            return 0

思路3：遍历数组的时候保存两个值：一个是数组的一个数字，一个是次数。时间复杂度是O(n)，空间复杂度O(1)

# -*- coding:utf-8 -*-
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        length = len(numbers)
        if (length == 0):
            return 0
        elif(length == 1):
            return numbers[0]
        else:
            # 初始化
            num = numbers[0]
            count = 1
            for i in range(1,length):
                if(count == 0):
                    num = numbers[i]
                    count = 1
                elif(numbers[i] == num):
                    count += 1
                else:
                    count -= 1
            if(numbers.count(num) > len(numbers)/2):
                return num
            return 0

关于时间复杂度的参考：
python sort函数内部实现原理
python基本数据类型的时间复杂度
python count实现可见 列表及操作count部分
Timsort原理介绍