What is the primary approach for solving the Least Number of Unique Integers after K Removals?

The primary approach involves counting the frequency of elements using a hash map, sorting them by frequency, and greedily removing the least frequent elements.

How does sorting by frequency help in the Least Number of Unique Integers after K Removals problem?

Sorting by frequency allows you to prioritize removing elements with the smallest counts first, minimizing the number of remaining unique integers.

What happens if k equals the length of the array?

If `k` equals the length of the array, all elements can be removed, leaving zero unique integers. The solution handles this case efficiently by iterating through all elements and removing them.

How do you optimize the solution for large arrays in the Least Number of Unique Integers after K Removals problem?

The solution is optimized by using hash maps to store frequencies, ensuring the complexity remains linear for counting, with the sorting operation being the only costly step (O(n log n)).

What is the worst-case time complexity of the Least Number of Unique Integers after K Removals?

The worst-case time complexity is O(n log n), where n is the length of the array, due to the sorting step. However, the overall process is efficient for large inputs.

#1481

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

不同整数的最少数目

给你一个整数数组 arr 和一个整数 k 。现需要从数组中恰好移除 k 个元素，请找出移除后数组中不同整数的最少数目。示例 1：输入： arr = [5,5,4], k = 1 输出： 1 解释：移除 1 个 4 ，数组中只剩下 5 一种整数。示例 2：输入： arr = [4,3,1,1…

数组哈希表贪心排序计数

题目描述

给你一个整数数组 arr 和一个整数 k 。现需要从数组中恰好移除 k 个元素，请找出移除后数组中不同整数的最少数目。

示例 1：

输入：arr = [5,5,4], k = 1
输出：1
解释：移除 1 个 4 ，数组中只剩下 5 一种整数。

示例 2：

输入：arr = [4,3,1,1,3,3,2], k = 3
输出：2
解释：先移除 4、2 ，然后再移除两个 1 中的任意 1 个或者三个 3 中的任意 1 个，最后剩下 1 和 3 两种整数。

提示：

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

lightbulb

解题思路

方法一：哈希表 + 排序

我们用哈希表 $cnt$ 统计数组 $arr$ 中每个整数出现的次数，然后将 $cnt$ 中的值按照从小到大的顺序排序，记录在数组 $nums$ 中。

接下来，我们遍历数组 $nums$ ，对于当前遍历到的每个值 $nums[i]$ ，我们将 $k$ 减去 $nums[i]$ ，如果 $k \lt 0$ ，则说明我们已经移除了 $k$ 个元素，此时数组中不同整数的最少数目为 $nums$ 的长度减去当前遍历到的下标 $i$ ，直接返回即可。

若遍历结束，说明我们移除了所有的元素，此时数组中不同整数的最少数目为 $0$ 。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $arr$ 的长度。

1

2

3

4

5

6

7

8

9

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        cnt = Counter(arr)
        for i, v in enumerate(sorted(cnt.values())):
            k -= v
            if k < 0:
                return len(cnt) - i
        return 0

speed

复杂度分析

指标	值
时间	O(n)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Candidate demonstrates proficiency in frequency counting and hash maps.
question_mark
Approach effectively uses a greedy strategy to minimize the number of unique integers.
question_mark
Candidate considers time complexity and implements an efficient solution.

warning

常见陷阱

外企场景

error
Not considering the greedy strategy of removing the least frequent elements first.
error
Incorrectly handling edge cases where k is 0 or the array has only one unique integer.
error
Failing to optimize the solution and resorting to unnecessary nested loops.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if `k` is equal to the length of the array?
arrow_right_alt
What if `k` is 0? How does the solution handle that?
arrow_right_alt
How does the solution scale with a large input size, such as when `arr.length` approaches 100,000?

help

常见问题

外企场景

继续练习

#1090 受标签影响的最大值 #1054 距离相等的条形码 #621 任务调度器