题解

要求选择 k 个数求出现次数最多的数最大是多少。

根据出现频率排序从小到大排序，并判断当前的数是否能在选中的数作为众数出现。

用一个变量 $t$ 记录已经选择的数字的总和，如果当前数字的频率加上 $t$ 以及剩余数字的最大贡献（即剩余数字个数乘以当前数字的频率）大于等于 $k$，就可以选择当前数字更新答案。

时间复杂度 $O(n \log n)$，空间复杂度 $O(n)$。

AC代码

Python

from collections import Counter
T = int(input())
for _ in range(T):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    d = Counter(a)
    v = []
    for kk, val in d.items():
        v.append((val, kk))
    v.sort()
    t = 0
    res = 0
    cnt = len(v)
    for L, R in v:
        cnt -= 1
        if L + t + cnt * L >= k:
            res = max(res, R) 
        t += L
    print(res)

java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();

        for (int t = 0; t < T; t++) {
            int n = scanner.nextInt();
            int k = scanner.nextInt();
            int[] a = new int[n];

            for (int i = 0; i < n; i++) {
                a[i] = scanner.nextInt();
            }

            // 计算频次
            Map<Integer, Integer> frequencyMap = new HashMap<>();
            for (int num : a) {
                frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
            }

            // 将频次与元素对存储在列表中
            List<int[]> v = new ArrayList<>();
            for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
                v.add(new int[]{entry.getValue(), entry.getKey()});
            }

            // 按频次升序排序
            v.sort((o1, o2) -> Integer.compare(o1[0], o2[0]));

            int tSum = 0;
            int res = 0;
            int cnt = v.size();

            // 寻找满足条件的最大元素
            for (int[] pair : v) {
                int L = pair[0];
                int R = pair[1];
                cnt--;

                if (L + tSum + cnt * L >= k) {
                    res = Math.max(res, R);
                }
                tSum += L;
            }

            System.out.println(res);
        }

        scanner.close();
    }
}

C++

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int t, n, k, a[N];
unordered_map<int,int> hmap;

bool cmp(int a, int b){
	return a > b;
}

int main(){
	scanf("%d", &t);
	while(t--){
		hmap.clear();
		scanf("%d%d", &n, &k);
		for(int i = 1; i <= n; i++) {
			scanf("%d", &a[i]);
			if(hmap.count(a[i]) == 0) hmap[a[i]] = 1;
			else hmap[a[i]]++;
		}
		sort(a + 1, a + n + 1, cmp);
		n = unique(a + 1, a + n + 1) - a - 1;
		//printf("n = %d\n", n);
		int ans = 0;
		while(k){
			ans = 0;
			for(int i = 1; i <= n && k; i++){
				if(hmap[a[i]]) {
					ans = max(ans, a[i]);
					k--;
					hmap[a[i]]--;
				}
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

小红的美食节

问题描述

小红是一位美食评论家，他最近参加了一个美食节，品尝了 $n$ 种不同的美食，每种美食都有一个特定的人气值。现在，小红想写一篇关于这次美食节的文章，他打算挑选出 $k$ 种美食，使得文章中能够突出一种特别受欢迎的美食。为了增加文章的吸引力，他希望选择的美食中，有一种美食的人气值能够尽可能高。

输入格式

本题有多组测试数据。

第一行一个正整数 $T$，表示数据的组数。

接下来，对于每组测试数据，输入包含两行：

第一行两个正整数 $n$ 和 $k$，表示美食的种类数和小红需要挑选的美食数量。

第二行 $n$ 个正整数，每个数表示一种美食的人气值。

输出格式

输出包含 $T$ 行，对于每个测试数据：

每行一个正整数，表示选出 $k$ 种美食组成的新美食列表中出现次数最多的美食的最大人气值。

样例输入

1
6 3
2 2 2 1 1 1

样例输出

2

评测数据与规模

• $1 \leq T \leq 100$
• $1 \leq k \leq n \leq 10^5$
• $1 \leq a_i \leq 10^9$