Java_21 完成一半题目

完成一半题目

有 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

我的解答

将知识点类型和在2N道题中出现的次数储存在哈希表中，类型为key,次数为value

再将哈希表根据value从大到小排序

根据value的累加和与N比较，大于等于时，看看是第几个value，即可判断知识点的类型

第一次解答错误，因为在存储次数times，下一个知识点类型的times未置1

完整代码，哈希表根据value从大到小排序还是网上借鉴的，还是不太建议用这个思路做吧

Java HashMap按key排序和按value排序的两种简便方法

class Solution {public int halfQuestions(int[] questions) {//将每种类型及其对应出现的次数存到哈希表中HashMap<Integer,Integer> h=new HashMap<Integer,Integer>();int i=0,j=0,times=1;for(i=0;i<questions.length;i++){if(questions[i]==0)continue;for(j=i+1;j<questions.length;j++){if(questions[i]==questions[j]){times=times+1;questions[j]=0;}}h.put(questions[i],times);times=1;}List<HashMap.Entry<Integer, Integer>> list = new ArrayList<HashMap.Entry<Integer, Integer>>(h.entrySet()); //转换为listlist.sort(new Comparator<HashMap.Entry<Integer, Integer>>() {@Overridepublic int compare(HashMap.Entry<Integer, Integer> o1, HashMap.Entry<Integer, Integer> o2) {return o2.getValue().compareTo(o1.getValue());}});int sum=0;for(i=0;i<list.size();i++){sum=sum+list.get(i).getValue();if(sum>=questions.length/2){return i+1;}}return -1;}
}