LeetCode动画 | 1338.数组大小减半
LeetCode动画 | 1338.数组大小减半
以下文章来源于算法无遗策 ，作者我脱下短袖
今天分享一个LeetCode题，题号是1338，标题是数组大小减半，题目标签是贪心算法和数组。
题目描述
给你一个整数数组 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}，结果数组为空。示例 3：
输入：arr = [1,9]
输出：1示例 4：
输入：arr = [1000,1000,3,7]
输出：1示例 5：
输入：arr = [1,2,3,4,5,6,7,8,9,10]
输出：5提示：
1 <= arr.length <= 10^5
arr.length 为偶数
1 <= arr[i] <= 10^5解题
此题题目标签是贪心算法，不过贪心贪心什么是贪心呢？
贪心算法的设计在于策略的选择，贪心算法是将求解的问题分解成若干个局部问题，而局部问题通过贪心得到最优解，一般取最大和最小值，或者某个极限。
所以贪心策略的选择适用于：局部最优策略从而达到全局的最优解。
回到题目描述，本题要求 至少 能删除数组的一半，即超过数组的一半，包含数组的一半。
再看示例1已经明确表示，大小为 2 的可行集合有 {3, 7}, {3, 5}, {3, 2}, {5, 2}，选择{2, 7}却不可行，这和贪心算法有什么关系呢？在于整数的出现次数。
因为题目描述已经明确数组的长度为偶数，所以，假设整个数组的长度为20，如果最大的出现次数为10次及10次以上，则直接返回1；如果最大的次数为9次，剩下的出现次数肯定会有1次，返回2；如果最大的次数为8，因为题目要求是 至少 ，所以要看看有没有出现次数是2次及2次以上，可以干脆找第二大的出现次数。
所以，通过贪心算法求解局部问题的最优策略，第一个局部问题通过贪心策略找最大的出现次数，如果没有超过数组的一半，则继续第二个局部问题，同样通过贪心策略找第二大的出现此处，以此类推，直到超过数组的一半，从而达到全局问题的最优解。
出现次数可以通过哈希表去统计，接着取出现次数进行排序，然后进行贪心策略，动画和代码如下：
动画
Code：使用哈希表
import java.util.Arrays;
import java.util.HashMap;
class Solution {
public int minSetSize(int[] arr) {
// 创建哈希表
HashMap<Integer, Integer> map = new HashMap<>();
for (int a : arr)
map.put(a, map.getOrDefault(a, 0) + 1);
// 创建数组
int[] lens = new int[map.size()]; // 各个值的数组长度
int index = 0;
for (int val : map.values()) {
lens[index] = val;
index++;
}
Arrays.sort(lens); // 排序 升序
// 题目描述已经说明 arr.length 为偶数
int len = arr.length / 2;
// 贪心 优先取最大的
for (int i = lens.length - 1; i >= 0; i--) {
len -= lens[i];
// 返回 至少 删除数组的一半
if (len <= 0) return lens.length - i;
}
return -1;
}
}但是我们看到题目描述的提示如下：
1 <= arr.length <= 10^5
1 <= arr[i] <= 10^5意味着可以直接使用数组计算，这样速度更快一点。
代码是将哈希表改为直接寻址表就可以了，代码如下：
Code：直接使用数组
import java.util.Arrays;
/**
* 1 <= arr.length <= 10^5
* arr.length 为偶数
* 1 <= arr[i] <= 10^5
*/
class Solution {
public int minSetSize(int[] arr) {
// 创建直接寻址表
int[] nums = new int[100001];
for (int num : arr)
nums[num]++;
// 排序 建议止于nums最后一个数
int maxLen = 0;
for (int i = 1; i < 100001; i++)
if (nums[i] != 0) maxLen = i;
Arrays.sort(nums, 0, maxLen); // 排序这个区间
int len = arr.length / 2;
// 贪心
for (int i = maxLen; i >= 1; i--) {
len -= nums[i];
if (len <= 0) return maxLen - i + 1;
}
return -1;
}
}