What is the core pattern for solving the Reduce Array Size to The Half problem?

The core pattern is array scanning plus hash lookup to count frequencies and then greedily removing the most frequent integers.

How do you reduce the array size to half in the least number of removals?

By selecting integers with the highest frequency and removing them, you can efficiently reduce the array size to at least half.

Can this problem be solved with a sliding window approach?

No, a sliding window is not applicable here. The problem requires counting frequencies and removing the most frequent elements directly.

What is the time complexity of this problem?

The time complexity is O(n log n) due to sorting the frequency counts, where n is the length of the array.

What should I focus on to solve this problem efficiently?

Focus on efficiently counting the frequencies of integers, sorting the counts, and removing the most frequent ones until half of the array is removed.

#1338

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

数组大小减半

给你一个整数数组 arr 。你可以从中选出一个整数集合，并删除这些整数在数组中的每次出现。返回至少能删除数组中的一半整数的整数集合的最小大小。示例 1：输入： arr = [3,3,3,3,5,5,5,2,2,7] 输出： 2 解释：选择 {3,7} 使得结果数组为 [5,5,5,2,2…

数组哈希表贪心排序堆（优先队列）

题目描述

给你一个整数数组 arr。你可以从中选出一个整数集合，并删除这些整数在数组中的每次出现。

返回至少能删除数组中的一半整数的整数集合的最小大小。

示例 1：

输入：arr = [3,3,3,3,5,5,5,2,2,7]
输出：2
解释：选择 {3,7} 使得结果数组为 [5,5,5,2,2]、长度为 5（原数组长度的一半）。
大小为 2 的可行集合有 {3,5},{3,2},{5,2}。
选择 {2,7} 是不可行的，它的结果数组为 [3,3,3,3,5,5,5]，新数组长度大于原数组的二分之一。

示例 2：

输入：arr = [7,7,7,7,7,7]
输出：1
解释：我们只能选择集合 {7}，结果数组为空。

提示：

1 <= arr.length <= 10⁵
arr.length 为偶数
1 <= arr[i] <= 10⁵

lightbulb

解题思路

方法一：计数 + 排序

我们可以用哈希表或数组 $cnt$ 统计数组 $\textit{arr}$ 中每个数字出现的次数，然后将 $cnt$ 中的数字从大到小排序，从大到小遍历 $\textit{cnt}$ ，每次遍历将当前数字 $x$ 加入答案，并将 $m$ 加上 $x$ ，如果 $m \geq \frac{n}{2}$ ，则返回答案。

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

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        cnt = Counter(arr)
        ans = m = 0
        for _, v in cnt.most_common():
            m += v
            ans += 1
            if m * 2 >= len(arr):
                break
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for an understanding of greedy algorithms and how to apply them efficiently.
question_mark
Check if the candidate can prioritize based on frequency counts for optimization.
question_mark
Evaluate if the candidate avoids unnecessary complexity by focusing on sorting and frequency analysis.

warning

常见陷阱

外企场景

error
Not sorting the frequency list and blindly removing random elements can lead to suboptimal solutions.
error
Failing to account for cases where only one integer needs removal.
error
Over-complicating the approach with unnecessary data structures or logic.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the array has no duplicates? This changes the dynamic of removal.
arrow_right_alt
What if you need to remove exactly half of the array, not just at least half?
arrow_right_alt
Consider situations where integers in the array are very large but their counts are small.

help

常见问题

外企场景

继续练习

#1054 距离相等的条形码 #632 最小区间 #621 任务调度器