首页 > 其他 > 详细

【leetcode】1481. Least Number of Unique Integers after K Removals

时间:2020-06-22 14:45:05      阅读:68      评论:0      收藏:0      [点我收藏+]

题目如下:

Given an array of integers arr and an integer k. Find the least number of unique integers after removing exactly k elements.

Example 1:

Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the single 4, only 5 is left.

Example 2:

Input: arr = [4,3,1,1,3,3,2], k = 3
Output: 2
Explanation: Remove 4, 2 and either one of the two 1s or three 3s. 1 and 3 will be left. 

Constraints:

  • 1 <= arr.length <= 10^5
  • 1 <= arr[i] <= 10^9
  • 0 <= k <= arr.length

解题思路:贪心算法, 从出现次数最少的元素删起,然后是次最少。

代码如下:

class Solution(object):
    def findLeastNumOfUniqueInts(self, arr, k):
        """
        :type arr: List[int]
        :type k: int
        :rtype: int
        """
        dic = {}
        for i in arr:
            dic[i] = dic.setdefault(i,0) + 1
        pair = []
        for key,val in dic.iteritems():
            pair.append((key,val))

        def cmpf(item1,item2):
            return item1[1] - item2[1]

        pair.sort(cmp=cmpf)

        while len(pair) > 0 and k > 0:
            key,val = pair.pop(0)
            if k >= val:
                k -= val
            else:
                pair.append((key,val))
                break

        return len(pair)

 

【leetcode】1481. Least Number of Unique Integers after K Removals

原文:https://www.cnblogs.com/seyjs/p/13176633.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!