class Solution {
public:
int halfQuestions(vector<int>& questions) {
}
};
LCS 02. 完成一半题目
有 N 位扣友参加了微软与力扣举办了「以扣会友」线下活动。主办方提供了 2*N 道题目，整型数组 questions 中每个数字对应了每道题目所涉及的知识点类型。
若每位扣友选择不同的一题，请返回被选的 N 道题目至少包含多少种知识点类型。
示例 1：
输入：
questions = [2,1,6,2]输出：
1解释：有 2 位扣友在 4 道题目中选择 2 题。 可选择完成知识点类型为 2 的题目时，此时仅一种知识点类型 因此至少包含 1 种知识点类型。
示例 2：
输入：
questions = [1,5,1,3,4,5,2,5,3,3,8,6]输出：
2解释：有 6 位扣友在 12 道题目中选择题目，需要选择 6 题。 选择完成知识点类型为 3、5 的题目，因此至少包含 2 种知识点类型。
提示：
questions.length == 2*n2 <= questions.length <= 10^51 <= questions[i] <= 1000原站题解
golang 解法, 执行用时: 68 ms, 内存消耗: 9 MB, 提交时间: 2021-07-01 16:22:47
func halfQuestions(questions []int) (ans int) {
cnt := [1001]int{}
for _, v := range questions {
cnt[v]++
}
sort.Ints(cnt[:])
for i, n := 1000, len(questions)/2; n > 0; i-- {
ans++
n -= cnt[i]
}
return
}
golang 解法, 执行用时: 104 ms, 内存消耗: 8.6 MB, 提交时间: 2021-07-01 16:20:46
func halfQuestions(questions []int) int {
// 从数组中选出一般, 种类最少
mp := make(map[int]int)
var arr []int
for _, question := range questions {
mp[question]++
if mp[question] == 1 {
arr = append(arr, question)
}
}
sort.Slice(arr, func(i, j int) bool {
return mp[arr[i]] > mp[arr[j]]
})
n := len(questions)/2
k := 1
t := 0
for k = 0; ; k++ {
if t+mp[arr[k]] >= n {
break
}
t += mp[arr[k]]
}
return k+1
}