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

1338. 数组大小减半

Hi 大家好,我是张小猪。欢迎来到『宝宝也能看懂』系列之 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%。

总结

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

相关链接

原文链接:segmentfault.com

上一篇:gulp-me
下一篇:Mock在Vue项目中的一点应用

相关推荐

  • 茄子算法每日N题之LeetCode面试题22. 链表中倒数第k个节点

    LeetCode 面试题22. 链表中倒数第k个节点 大家好,我是灵魂画师茄子。技术水平一般,喜欢画画。 开始今天的正题。 leetCode面试题22. 链表中倒数第k个节点 输入一个链表,输出该链表...

    21 天前
  • 茄子算法每日N题之LeetCode面试题 02.01. 移除重复节点

    LeetCode 面试题 02.01. 移除重复节点 大家好,我是灵魂画师茄子。技术水平一般,喜欢画画。 开始今天的正题。 leetCode面试题 02.01. 移除重复节点 编写代码,移除未排序链表...

    20 天前
  • 茄子算法每日N题之LeetCode876链表的中间结点

    LeetCode 876.链表的中间结点 大家好,我是灵魂画师茄子。技术水平一般,喜欢画画。 开始今天的正题。 给定一个带有头结点 head 的非空单链表,返回链表的中间结点。

    1 个月前
  • 茄子算法每日N题之LeetCode86. 分隔链表

    LeetCode 86. 分隔链表 大家好,我是灵魂画师茄子。技术水平一般,喜欢画画。 开始今天的正题。 leetCode86.分隔链表 给定一个链表和一个特定值 x,对链表进行分隔,使得所有小于 x...

    22 天前
  • 茄子算法每日N题之LeetCode83删除排序链表中的重复元素

    LeetCode 83.删除排序链表中的重复元素|| 大家好,我是灵魂画师茄子。技术水平一般,喜欢画画。 开始今天的正题。 leetCode83删除排序链表中的重复元素 给定一个排序链表,删除所有重复...

    1 个月前
  • 茄子算法每日N题之LeetCode45跳跃游戏 II

    LeetCode 45.跳跃游戏 II 大家好,我是灵魂画师茄子。技术水平一般,喜欢画画。 开始今天的正题。 leetCode45.跳跃游戏 II(每日一题/5月4日) 给定一个非负整数数组,你最初位...

    1 个月前
  • 茄子算法每日N题之LeetCode25K个一组翻转链表

    LeetCode 25.K个一组翻转链表 大家好,我是灵魂画师茄子。技术水平一般,喜欢画画。 开始今天的正题。 给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。

    1 个月前
  • 茄子算法每日N题之LeetCode24两两交换链表中的节点

    LeetCode 24.两两交换链表中的节点 大家好,我是灵魂画师茄子。技术水平一般,喜欢画画。 开始今天的正题。 给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。

    1 个月前
  • 茄子算法每日N题之LeetCode23.合并K个排序链表

    LeetCode 23.合并K个排序链表 大家好,我是灵魂画师茄子。技术水平一般,喜欢画画。 开始今天的正题。 23.合并K个排序链表 合并 k 个排序链表,返回合并后的排序链表。

    23 天前
  • 茄子算法每日N题之LeetCode207移除链表元素

    LeetCode 207.移除链表元素 大家好,我是灵魂画师茄子。技术水平一般,喜欢画画。 开始今天的正题。 删除链表中等于给定值 val 的所有节点。 示例: 输入: 1&gt;2&gt;6&gt;...

    1 个月前

官方社区

扫码加入 JavaScript 社区