LeetCode 1338中等贪心/哈希
数组大小减半 图解题解
这道题到底在问什么
给定整数数组 arr。每次操作选定一个数值,删除数组中所有等于该值的元素。求至少选择多少种不同数值,才能让剩余长度减少至少一半。
- 输入
- arr=[3,3,3,3,5,5,5,2,2,7]
- 输出
- 2 （删 3 和 5 共去掉 7 个,超过一半 5 个）
- 输入
- arr=[7,7,7,7,7,7]
- 输出
- 1 （只删 7 即可去掉全部 6 个）
最优解：一步一步想明白
- 3记住「先数次数,再按次数从大到小删,够一半就停」，下面每帧都在套它。
- 4第一段:从左到右扫数组，每遇到一个数值，就在「值 → 出现次数」表里给它加一。
- 5扫到第 0 个，是数值 3。这是第一次出现，表里还没有它，准备给它新开一行从 1 开始数。
- 6数值 3 的出现次数更新到 1（高亮行）。继续往后扫。
- 7扫到第 1 个，是数值 3（绿色是它之前出现过的位置）。给它的出现次数加一。
- 8数值 3 的出现次数更新到 2（高亮行）。继续往后扫。
- 9扫到第 2 个，是数值 3（绿色是它之前出现过的位置）。给它的出现次数加一。
- 10数值 3 的出现次数更新到 3（高亮行）。继续往后扫。
- 11扫到第 3 个，是数值 3（绿色是它之前出现过的位置）。给它的出现次数加一。
- 12数值 3 的出现次数更新到 4（高亮行）。继续往后扫。
- 13扫到第 4 个，是数值 5。这是第一次出现，表里还没有它，准备给它新开一行从 1 开始数。
- 14数值 5 的出现次数更新到 1（高亮行）。继续往后扫。
- 15扫到第 5 个，是数值 5（绿色是它之前出现过的位置）。给它的出现次数加一。
- 16数值 5 的出现次数更新到 2（高亮行）。继续往后扫。
- 17扫到第 6 个，是数值 5（绿色是它之前出现过的位置）。给它的出现次数加一。
- 18数值 5 的出现次数更新到 3（高亮行）。继续往后扫。
- 19扫到第 7 个，是数值 2。这是第一次出现，表里还没有它，准备给它新开一行从 1 开始数。
- 20数值 2 的出现次数更新到 1（高亮行）。继续往后扫。
- 21扫到第 8 个，是数值 2（绿色是它之前出现过的位置）。给它的出现次数加一。
- 22数值 2 的出现次数更新到 2（高亮行）。继续往后扫。
- 23扫到第 9 个，是数值 7。这是第一次出现，表里还没有它，准备给它新开一行从 1 开始数。
- 24数值 7 的出现次数更新到 1（高亮行）。继续往后扫。
- 25第一段扫完。各数值的出现次数是 3→4，5→3，2→2，7→1。接下来第二段:把这些次数从大到小排好,逐个累加删除。
- 26把次数从大到小排好:4 ≥ 3 ≥ 2 ≥ 1。第二段从最大的开始删,每删一种,累计删除量增加,达到 5 个就停。
- 27当前剩下里次数最多的是数值 3（出现 4 次,绿色这些位置）。选它,这是第 1 种被删的值。
- 28删掉数值 3 后累计删了 4 个（红色）。4×2 = 8 还 < 10，没到一半,继续删下一个次数最大的值。
- 29当前剩下里次数最多的是数值 5（出现 3 次,绿色这些位置）。选它,这是第 2 种被删的值。
- 30删掉数值 5 后累计删了 7 个（红色）。7×2 = 14 ≥ 10，已达到一半！选了 2 种就停。
- 31从次数最大的往下删,删到 3、5 这 2 种时累计删了 7 个（红色），已超过一半 5。所以最少选 2 种数值。
⚠️ 容易写错的地方
✗ 错：只数总长一半的个数就停
✓ 对：要按「次数从大到小」删才最省种类
同样删够一半,优先删数量多的值用到的种类最少（贪心）
✗ 错：把判定写成 removed ≥ n/2 用整除
✓ 对：用 removed×2 ≥ n 避免奇数长度时少删
n 为奇数时 n/2 整除会偏小,可能误判提前达标
✗ 错：比较「值」的大小来排序
✓ 对：排序的依据是「出现次数」不是值本身
贪心比的是每种值能删掉多少个,即它的次数
完整代码（Python / C++ / Java）
Python
from typing import List
from collections import Counter
class Solution:
def minSetSize(self, arr: List[int]) -> int:
counts = sorted(Counter(arr).values(), reverse=True)
removed = 0
for i, c in enumerate(counts, 1):
removed += c
if removed * 2 >= len(arr):
return i
return 0C++
#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;
class Solution {
public:
int minSetSize(vector<int>& arr) {
unordered_map<int,int> count;
for (int x : arr) count[x]++;
vector<int> freq;
for (auto &p : count) freq.push_back(p.second);
sort(freq.rbegin(), freq.rend());
int removed = 0;
for (int i = 0; i < (int)freq.size(); ++i) {
removed += freq[i];
if (removed * 2 >= (int)arr.size()) return i + 1;
}
return 0;
}
};Java
import java.util.*;
class Solution {
public int minSetSize(int[] arr) {
Map<Integer, Integer> count = new HashMap<>();
for (int x : arr) count.put(x, count.getOrDefault(x, 0) + 1);
List<Integer> freq = new ArrayList<>(count.values());
freq.sort(Collections.reverseOrder());
int removed = 0;
for (int i = 0; i < freq.size(); i++) {
removed += freq.get(i);
if (removed * 2 >= arr.length) return i + 1;
}
return 0;
}
}复杂度
时间
O(n log n)
计数 O(n);对 k 个不同次数降序排序 O(k log k) ≤ O(n log n)
空间
O(n)
计数表与次数数组,最多 n 个不同值
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 数组大小减半 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
能不能不排序,用更快的方法？+
可以。次数最大不超过 n,可用「桶/计数排序」按次数分桶,从大桶往小桶取,做到 O(n)。但用通用排序写起来最直观,n 不大时差别不重要。识别出「桶排序可去掉 log」是加分项。
这题考的核心思维是什么？+
两步:先把元素映射成「频率」(哈希计数),再对频率做贪心(降序累加到阈值)。很多「最少操作 / 最多收益」的题都能套这个「计数 + 按频率贪心」框架。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 数组大小减半 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。