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*n
• 2 <= questions.length <= 10^5
• 1 <= questions[i] <= 1000

解法

统计各个问题类型出现的次数，按照次数降序排列。

然后依次选择问题类型，直至满足条件。

Python3

class Solution:
    def halfQuestions(self, questions: List[int]) -> int:
        counter = collections.Counter(questions)
        counter = OrderedDict(counter.most_common())
        n = len(questions) >> 1
        res = 0
        for v in counter.values():
            res += 1
            if v >= n:
                return res
            n -= v
        return res

Java

class Solution {
    public int halfQuestions(int[] questions) {
        int[] counter = new int[1010];
        for (int e : questions) {
            ++counter[e];
        }
        int n = questions.length >> 1;
        Arrays.sort(counter);
        int res = 0;
        for (int i = counter.length - 1; i >= 0; --i) {
            ++res;
            if (counter[i] >= n) {
                return res;
            }
            n -= counter[i];
        }
        return res;
    }
}

C++

class Solution {
public:
    int halfQuestions(vector<int>& questions) {
        vector<int> counter(1010);
        for (int e : questions) ++counter[e];
        int n = questions.size() >> 1;
        sort(counter.begin(), counter.end());
        int res = 0;
        for (int i = counter.size() - 1; i >= 0; --i)
        {
            ++res;
            if (counter[i] >= n) return res;
            n -= counter[i];
        }
        return res;
    }
};

Go

func halfQuestions(questions []int) int {
	counter := make([]int, 1010)
	for _, e := range questions {
		counter[e]++
	}
	n := len(questions) >> 1
	sort.Ints(counter)
	res := 0
	for i := len(counter) - 1; i >= 0; i-- {
		res++
		if counter[i] >= n {
			return res
		}
		n -= counter[i]
	}
	return res
}

...