题目一

题目描述

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

解题思路

思路一：基于快排思想

思路二：如果有符合条件的数字，则它出现的次数比其他所有数字出现的次数和还要多。

在遍历数组时保存两个值：一是数组中一个数字，一是次数。遍历下一个数字时，若它与之前保存的数字相同，则次数加1，否则次数减1；若次数为0，则保存下一个数字，并将次数置为1。遍历结束后，所保存的数字即为所求。然后再判断它是否符合条件即可。

代码实现

思路二：

# -*- coding:utf-8 -*-
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        if not numbers:
            return 0
        res = 0
        times = 0
        for i, num in enumerate(numbers):
            if times == 0:
                res = num
                times = 1
            elif num == res:
                times += 1
            else:
                times -= 1
        print times
        return res if  numbers.count(res) > len(numbers)//2 else 0

题目二

题目描述

给定一个整型数组arr，再给定一个整数k，打印所有出现次数大于n/k的数，如果没有这样的数,请打印”-1“。

题目来源：https://www.nowcoder.com/practice/4d448650c0324df08c40c614226026ad?tpId=101&tqId=33223&tPage=1&rp=1&ru=/ta/programmer-code-interview-guide&qru=/ta/programmer-code-interview-guide/question-ranking

解题思路

一次在数组中删掉k个不同的数，不停地删除，直到剩下的数的种类不足k就停止删除，那么一个数如果在数组中出现的次数大于n/k，则最后这个数一定会剩下来。

对于上一题，一次在数组中删掉两个不同的数，不停地删除，直到剩下的数只有一种，如果一个数出现的次数大于n/2，那么这个数一定是最后剩下来的一种数。

上一题的解决办法是，有一个候选数res，以及这个候选的times统计，那么这道题需要k-1个候选和k-1个times统计即可

1、候选表 HashMap：key为（K - 1）个候选 candiate，value 为它们分别出现的次数;

2、遍历到 arr[i] 时，看 arr[i] 是否在候选人中，如果与某一个候选人相同，就把属于那个候选的点数统计加 1，如果与所有的候选都不相同，先看当前的候选是否选满了，候选表中的大小为 K - 1 个，就是满了；否则就是没有选满。

2.1、如果不满，则把 arr[i] 作为一个新的候选，属于它的点数初始化为 1；
2.2、如果已满，说明此时发现了 k 个不同的数，arr[i] 就是第 k 个。此时把每一个候选各自的点数全部减 1，表示每个候选“付出”一个自己的点数，当前数也不要。如果某些候选的点数在减 1 之后等于 0，则还需要把这些候选人从候选表中删除，候选又变为不满的状态。
在上述过程结束后，还需要再遍历一次，验证被选出来的所有候选有哪些出现次数真的大于 N / K。

代码实现

n, k = map(int, input().split())
arr = list(map(int, input().split()))
a = []
d = {}
def minusOne(d):
    temp = []
    for key, v in d.items():
        if v == 1:
            temp.append(key)
        else:
            d[key] = v - 1
    for i in temp:
        d.pop(i)
 
for i in arr:
    if i in d:
        d[i] += 1
    else:
        if len(d) == k - 1:
            minusOne(d)
        else:
            d[i] = 1
real = {}
for i in arr:
    if i in d:
        real[i] = real.get(i, 0) + 1
for key in d.keys():
    if real[key] > n / k:
        a.append(key)
if len(a) == 0:
    print('-1')
else:
    print(' '.join(map(str, [i for i in a])))