在数组中找到出现次数大于n/k的数

在数组中找到出现次数大于n/k的数

题目描述

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

输入描述：

输入包含两行，第一行输入包含两个整数n和k ( 1 ≤ k ≤ n ≤ 1 0 5 ) (1 \leq k \leq n \leq 10^5) (1≤k≤n≤105),第二行包含n个整数，代表数组 a r r ( 1 ≤ a r r i ≤ 1 0 9 ) arr(1 \leq arr_i \leq 10^9) arr(1≤arri​≤109)。

输出描述：

输出所有出现次数大于n/k的数，如果没有这样的数,请输出”-1“。

示例1

输入

7 7
1 2 3 1 2 3 4

输出

1 2 3

示例2

输入

4 1
1 1 2 3

输出

-1

备注：

时间复杂度 O ( n ) O(n) O(n),额外空间复杂度 O ( k ) O(k) O(k)。

---

题解：

参考 在数组中找到出现次数大于一半的数，在本题中，我们每次删除 k 个不同的元素，直到剩余的元素种类不足 k ，最终保留下来的一定是出现次数超过 n/k 的元素。

代码：

#include <cstdio>
#include <unordered_map>

using namespace std;

const int N = 100010;
int n, k;
int a[N];
unordered_map<int, int> Hash;

int main(void) {
    scanf("%d%d", &n, &k);
    for ( int i = 0; i < n; ++i ) {
        scanf("%d", a + i);
        if ( Hash.count( a[i] ) )
            Hash[ a[i] ] += 1;
        else {
            if ( Hash.size() == k - 1 ) {
                for ( auto it : Hash ) {
                    if ( --it.second == 0 ) Hash.erase( it.first );
                }
            } else Hash[ a[i] ] = 1;
        }
    }
    k = n / k;
    bool flag = false;
    for ( int i = 0; i < n; ++i ) {
        if ( Hash.count( a[i] ) && Hash[ a[i] ] > k ) {
            flag = true;
            printf("%d ", a[i]);
            Hash.erase( a[i] );
        }
    }
    if ( !flag ) return 0 * puts("-1");
    return 0;
}