完成一半题目

LCS 02. 完成一半题目

难度简单1

有 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

贪心

优先选择题目数量最多的知识点，只有当题目最多的知识点用完了之后，才去找下一个题目数量最多的知识点。首先统计每个知识点对应的题目的数量，统计完成后进行排序，按照从大到小的顺序一一选择知识点，直到人数被用完。

class Solution {
    public int halfQuestions(int[] questions) {
        int n = questions.length;
        int N = n/2;
        int[] hash = new int[1001];
        for(int question: questions){
            hash[question] ++;
        }

        Arrays.sort(hash);
        int cnt=0 ;
        for(int i=1000;i>=0;i--){
            if(N<=0){
                return cnt;
            }
            N-=hash[i];
            cnt++;
        }
        return 0;
    }
}

赏

谢谢你请我吃糖果

微信