【有书共读】《算法与数据结构题目最优解》（在线编程题总结8）

该书第八章——《数组与矩阵问题》，这部分我列举几个常见的面试题。见我的个人博客：https://blog.csdn.net/zichen_ziqi/article/details/82116525与https://blog.csdn.net/zichen_ziqi/article/details/81417262。主要包括两部分：数组中出现次数超过一半的一般的数字与无序数组中找出何为N的两个数（三个数，四个数）。暂时介绍第一部分，第二部分见详细的链接。

题目描述——网址，参考：大神解答

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

1、解法一——时间复杂度为O(N^2)

思路1：简单粗暴，双重循环遍历，找出现次数最多的那个数，再比较出现次数是否超过数组的一半。不详写，谁都能想到。

思路2：时间复杂度为O(N^2)的排序算法（如冒泡、插入、选择等）+ 求排序后数组的中间数 + 判断中间数出现次数是否超过数组的一半，这部分放在解法二中统一总结。

2、解法二——时间复杂度为O(NlogN)，

思路：数组排序后，如果符合条件的数存在，则一定是数组中间那个数。（比如：1，2，2，2，3；或2，2，2，3，4；或2，3，4，4，4等等），这种方法虽然容易理解，但由于涉及到快排sort，其时间复杂度为O(NlogN)并非最优。

def MoreThanHalfNum_Solution(numbers):
    len1 = len(numbers)
    if len1==0:
        return 0
    numbers.sort() # 排序
    middle = numbers[len1 // 2] #取排序后的中位数
 
    # 判断res是否符合条件，即出现次数大于数组长度的一半
    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

这里可能存在疑问，因为大家都知道非比较排序算法的时间复杂度为O(N)，这样最终的时间复杂度也是O(N)！；如果面试的过程中，面试官要求给定的无序数组，不能进行排序又该如何处理？

3、解法三——时间复杂度为O(N)——面试官想要的答案
（1）基于Partition函数的算法，见链接
（2）根据数组特点求解（重点）——剑指offer代码链接
如果有符合条件的数字，则它出现的次数比其他所有数字出现的次数和还要多。
思路：在遍历数组时保存两个值：一是数组中一个数字，一是次数。遍历下一个数字时，若它与之前保存的数字相同，则次数加1，否则次数减1；若次数为0，则保存下一个数字，并将次数置为1。遍历结束后，所保存的数字即为所求。然后再判断它是否符合条件即可。
参考代码为：

def MoreThanHalfNum_Solution(numbers):
    len1 = len(numbers)
    if len1==0:
        return 0
    elif len1>=1:
        # 遍历每个元素，并记录次数；若与前一个元素相同，则次数加1，否则次数减1
        res = numbers[0] # 初始值
        count = 1 # 次数
        for i in range(1,len1):
            if count == 0:
                # 更新result的值为当前元素，并置次数为1
                res = numbers[i]
                count = 1
            elif numbers[i] == res:
                count += 1 # 相同则加1
            elif numbers[i] != res:
                count -= 1 # # 不同则加1
 
        # 判断res是否符合条件，即出现次数大于数组长度的一半
        counts = 0
        for j in range(len1):
            if numbers[j] == res:
                counts += 1
        if counts>len1//2: # python3整除为//，python2为/
            return res
        else:
            return 0
 
 
if __name__ == '__main__':
    try:
        while True:
            arr = [int(i) for i in input().split()]
            print(MoreThanHalfNum_Solution(arr))
    except:
        pass

（3）Python中的cellection包的使用——参考Python collection的使用&代码链接

例子1、若想统计相关元素出现的次数，可以使用Counter：

>from collections import Counter
>cnt=Counter()
>for w in ['a','b','a','a','a','r','b']:
    cnt[w]+=1
Counter({'a': 4, 'b': 2, 'r': 1})
# 统计字符串出现的次数 前面有统计sen='hello world'，用defaultdict(int)
>cnt = Counter()
> for ch in 'hello':
    cnt[ch] = cnt[ch] + 1
Counter({'l': 2, 'o': 1, 'h': 1, 'e': 1})

例子2、：elements()方法按照元素的出现次数返回一个iterator(迭代器)，元素以任意的顺序返回，如果元素的计数小于1，将忽略它。

>c = Counter(a=4, b=3, c=1, d=-4,e=0)
Counter({'a': 4, 'b': 3, 'c': 1, 'd': -4, 'e':0})
>sorted(c.elements())
['a', 'a', 'a', 'a', 'b', 'b','b','c']
# most_common(n)返回一个list, list中包含Counter对象中出现最多前n个元素。
>c = Counter('abracadabra')
Counter({'a': 5, 'b': 2, 'r': 2, 'd': 1, 'c': 1})
>c.most_common(3)
[('a', 5), ('b', 2), ('r', 2)]

因此如果直接利用这个cellection包，上面的代码可写为：

import collections
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        tmp = collections.Counter(numbers)
        x = len(numbers)/2
        for k, v in tmp.items():
            if v > x:
                return k
        return 0

（4）用字典的键值对实现，参考：链接

用字典的键值对实现，键存放数组中的数字，值存放数字出现的次数。参考代码如下：

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

#笔试题目##算法工程师##秋招#