Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

LeetCode 200 simple questions

Topic describes

N friends participated in the offline activity of “Meeting friends with Friends” held by Microsoft and Licuo. The organizer provides 2*N questions. Each number in the integer array “questions” corresponds to the knowledge point type involved in each question. If each member chooses a different topic, please return the selected N topic contains at least how many knowledge types.

The sample1Questions = [2.1.6.2] output:1Explanation:2A button in the4Choose from the questions2The topic. The knowledge point type can be selected as2At this time, there is only one knowledge point type, so at least include1Kind of knowledge point type.Copy the code
The sample2Questions = [1.5.1.3.4.5.2.5.3.3.8.6] output:2Explanation:6A button in the12To choose a topic, you need to choose6The topic. Select complete knowledge point type as3,5The title, therefore, contains at least2Kind of knowledge point type.Copy the code

prompt

  • questions.length == 2*n
  • 2 <= questions.length <= 10^5
  • 1 <= questions[i] <= 1000

Their thinking

Record the frequency of appearance of each knowledge point type in questions, sort in ascending order according to the dictionary value(frequency of occurrence), and finally subtract target(number of people) from back to front.

def halfQuestions(self, questions) :
    """ :type questions: List[int] :rtype: int """
    dic = {}
    # Loop the number of occurrences of knowledge points
    for num in questions:
        dic[num] = dic.get(num, 0) + 1
    Sort the dictionary by value
    count_list = sorted(dic.items(), key=lambda x: x[1], reverse=False)
    res = 0
    target = len(questions)/2
    while target > 0:
        target -= count_list.pop()[1]
        res += 1
    return res
Copy the code

Clocked in today, the current progress 1/200.