current position:Home>leetcode 1338. Reduce Array Size to The Half(python)

leetcode 1338. Reduce Array Size to The Half(python)

2022-01-31 23:43:13 Wang Daya

「 This is my participation 11 The fourth of the yuegengwen challenge 20 God , Check out the activity details :2021 One last more challenge

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,5] which has size greater than half of the size of the old array.
 Copy code 

Example 2:

Input: arr = [7,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 code 

Example 3:

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

Example 4:

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

Example 5:

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

Note:

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

analysis

According to the meaning , Given an array of integers arr. You can select a set of integers and delete all those integers that have appeared in the array . The question asks us to return the size of the smallest set , To delete at least half of the integers in the array . I'm a little confused about the restrictions in the title , Has been clearly told arr.length It's even , But then he said arr.length Greater than or equal to 1 Less than or equal to 10^5 ,are you kiding ? Is it because I didn't learn math well 1 How can it be even ?

The idea is simple :

  • Initialization result result by 0 ,L by arr Half the length , Use built-in functions Counter Yes arr Count
  • Count the results according to value Descending order , Traverse all key value pairs , as long as L Greater than 0 Just result Add one , meanwhile L reduce value , Cycle this process until break , This can remove the least number and delete more than half of the integers
  • Finally back to 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 code 

Running results

Runtime: 640 ms, faster than 52.86% of Python online submissions for Reduce Array Size to The Half.
Memory Usage: 37.3 MB, less than 35.71% of Python online submissions for Reduce Array Size to The Half.
 Copy code 

Original link :leetcode.com/problems/re…

Your support is my greatest motivation

copyright notice
author[Wang Daya],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/01/202201312343110558.html

Random recommended