宝宝也能看懂的 leetcode 周赛 - 174 - 2

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

官方难度

MEDIUM

解决思路

嘛，这道题就很直白，没什么包装，导致小猪都不知道该写些什么啦。出题的小可爱，小猪讨厌你！哼 >.<

由于题目需要的是用最少的次数删掉一半及以上的数据，那么小猪看完之后的第一反应就是，我们是不是应该每次都选剩下的数据中最多数量的那个删除呢？由于各个数据之间没有任何联系，并且对于删除数据的要求只有一条，即相同的数字，那么这种思路其实是能直接得到最优解的。

相信细心的小伙伴已经发现啦，其实这就是用局部最优解累积得到全局最优解的过程，也就是贪心算法啦。

直接方案

基于上面的思路，我们可以得到下面的流程：

1. 对原始数据进行计数统计。
2. 按照降序排序。
3. 对排序的结果逐渐求和，直到和大于等于原始数据长度的一半。

基于这个流程，我们可以实现类似下面的代码：

const minSetSize = arr => {
  const LEN = arr.length;
  if (LEN < 3) return 1;

  const max = Math.max(...arr);
  const freq = new Uint16Array(max + 1);
  for (const val of arr) ++freq[val];

  let step = 0;
  let sum = 0;
  freq.sort((a, b) => b - a);
  for (const val of freq) {
    sum += val;
    ++step;
    if (sum >= LEN / 2) return step;
  }
};

这段代码跑了 96ms，暂时 beats 100%。

优化

上面的代码我们对统计计数进行了传统排序，复杂度就达到了 O(nlogn)。我们是否有方法降低这个复杂度呢？

这里介绍一种不那么传统的排序方式 -- 桶排序。我们先来看一个栗子：

我们现在假设有 2000 个学生，他们刚进行完一次考试，每个人考试成绩的范围是 [1, 100]。现在我们需要把他们这一次考试的成绩按照升序进行排序。

由于他们的考试成绩的范围并不大，我们可以先假设现在有 100 个桶，正好覆盖了每一个成绩的可能。然后我们把 1 分的试卷放进 1 号桶，把 2 分的试卷放进 2 号桶。以此类推，直到所有的试卷都放进了这 100 个桶子。不知道小伙伴们有没有发现，这时候我们其实就已经完成了对这 2000 份试卷的排序。我们只需要从低到高的查看每一个桶子里试卷的数量即可。

这种排序方式有个非常大的优势，即它的时间复杂度只有 O(n)，优于传统的基于比较和交换的排序算法。不过它也有很大的限制，需要我们能举出所有的可能。并且如果这个范围太大的话，需要排序的数据量又比较小，那么也会得不偿失。

基于上面介绍的这种桶排序，我们回到这道题目，可以得到如下的流程：

1. 对原始数据进行计数统计。
2. 基于桶排序进行排序，并记录每种计数频次的数据的数量。
3. 从大到小的遍历结果并求和，直到和大于等于原始数据长度的一半。

基于这个流程，我们可以实现类似下面的代码：

const minSetSize = arr => {
  const LEN = arr.length;
  if (LEN < 3) return 1;

  const max = Math.max(...arr);
  const freq = new Uint16Array(max + 1);
  let maxFreq = 0;
  for (const val of arr) ++freq[val] > maxFreq && (maxFreq = freq[val]);

  const freqBased = new Uint32Array(maxFreq + 1);
  for (const val of freq) ++freqBased[val];

  let step = 0;
  let sum = 0;
  for (let i = maxFreq; i >= 1; --i) {
    while (freqBased[i]--) {
      sum += i;
      ++step;
      if (sum >= LEN / 2) return step;
    }
  }
};

这段代码跑了 80ms，取代了上面的代码暂时 beats 100%。

总结

这道题本身其实非常直白，思路也很直接。所以在优化过程中，引入了一种不是特别常见的排序方式，并进行了说明。希望还没有接触过的小伙伴们能有所收获。