题目描述
有 N
位扣友参加了微软与力扣举办了「以扣会友」线下活动。主办方提供了 2*N
道题目,整型数组 questions
中每个数字对应了每道题目所涉及的知识点类型。
若每位扣友选择不同的一题,请返回被选的 N
道题目至少包含多少种知识点类型。
样例
输入:questions = [2,1,6,2]
输出:1
解释:有 2 位扣友在 4 道题目中选择 2 题。
可选择完成知识点类型为 2 的题目时,此时仅一种知识点类型
因此至少包含 1 种知识点类型。
输入:questions = [1,5,1,3,4,5,2,5,3,3,8,6]
输出:2
解释:有 6 位扣友在 12 道题目中选择题目,需要选择 6 题。
选择完成知识点类型为 3、5 的题目,因此至少包含 2 种知识点类型。
限制
questions.length == 2*n
2 <= questions.length <= 10^5
1 <= questions[i] <= 1000
算法
(贪心,哈希表) $O(n + m \log m)$
- 统计每个数字出现的个数,然后将频次数组从大到小排序。尽量选择知识点类型相同的题目。
- 遍历频次数组,找到答案。
时间复杂度
- 假设 $m$ 为不同类型的个数。
- 统计频次数组的时间复杂度为 $O(n)$,排序的时间复杂度为 $O(m \log m)$。
- 找答案的时间复杂度为 $O(m)$。
- 故总时间复杂度为 $O(n + m \log m)$。
空间复杂度
- 需要 $O(m)$ 的额外空间存储频次数组。
C++ 代码
const int M = 1000;
class Solution {
private:
int types[M];
public:
int halfQuestions(vector<int>& questions) {
for (int x : questions)
types[x - 1]++;
sort(types, types + M, [](int x, int y) {
return x > y;
});
int n = questions.size() / 2;
int ans = 0;
for (int i = 0; n > 0; i++) {
n -= types[i];
ans++;
}
return ans;
}
};