“This is the 20th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

describe

You are given an integer array arr. You can choose a set of integers and remove all the occurrences of these integers in the array.

Return the minimum size of the set so that at least half of the integers of the array are removed.

Example 1:

Input: arr = [3,3,3,3,5,5,5,2,2,7] Output: 2 Explanation: Choosing {3,7} will make the new array [5,5,5,2,2] which has size 5 (i.e equal to half of the size of the old array). Possible sets of size 2 are {3,5},{3,2},{5,2}. Choosing set {2,7} is not Possible as it will make the new array [3,3,3,3,5,5] which has size greater than half of the size of the old array.Copy the code

Example 2:

Input: arr = [7,7,7,7,7] Output: 1 Explanation: The only possible set you can choose is {7}. This will make the new array empty.Copy the code

Example 3:

Input: arr = [1,9]
Output: 1
Copy the code

Example 4:

Input: arr = [1000,1000,3,7]
Output: 1
Copy the code

Example 5:

Input: arr = [1,2,3,4,5,6,7,8,9,10]
Output: 5
Copy the code

Note:

1 <= arr.length <= 10^5
arr.length is even.
1 <= arr[i] <= 10^5
Copy the code

parsing

Given an integer array arr. You can select a set of integers and delete all those integers that appear in the array. They ask us to return the size of the minimum set so that we can delete at least half of the integers in the array. Arr. Length is an even number, but arr. Length is greater than or equal to 1 and less than or equal to 10^5. Am I bad at math? How can one be even?

The idea is simple:

  • The initialization result is 0, L is half the length of arR, and the arR is counted using the built-in function Counter
  • The counting results are arranged in descending order of value, and all key-value pairs are traversed. As long as L is greater than 0, result is increased by one, while L is reduced by value, and the process is repeated until break. In this way, the least number can be removed and more than half of the integers can be deleted
  • Return result

answer

class Solution(object):
    def minSetSize(self, arr):
        """
        :type arr: List[int]
        :rtype: int
        """
        c = collections.Counter(arr)
        L = len(arr)//2
        result = 0
        for k,v in sorted(c.items(), key=lambda x:-x[1]):
            if L>0:
                result += 1
                L -= v
            else:
                break
        return result
                
        	      
		
Copy the code

The results

Given The given list in The Python online submissions in The linked list. The linked submissions in The Python online submissions list Reduce Array Size to The Half.Copy the code

Original link: leetcode.com/problems/re…

Your support is my biggest motivation