专栏首页脑洞前端宝宝也能看懂的 leetcode 周赛 - 174 - 2

宝宝也能看懂的 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%。

总结

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

本文分享自微信公众号 - 脑洞前端(fe_lucifer)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-03-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【leetcode系列】172. 阶乘后的零

    我们需要求解这n个数字相乘的结果末尾有多少个0,由于题目要求log的复杂度,因此暴力求解是不行的。

    lucifer210
  • 【leetcode系列】136. 只出现一次的数字

    https://leetcode.com/problems/single-number/description/

    lucifer210
  • 371. 两整数之和

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/sum-of-two-integers 著作权归领扣网络...

    lucifer210
  • 【Scikit-Learn 中文文档 】安装 scikit-learn | ApacheCN

    中文文档: http://sklearn.apachecn.org/cn/0.19.0/tutorial/basic/tutorial.html 英文文档:...

    片刻
  • 手把手教你用神器nextjs一键导出你的github博客文章生成静态html!

    相信有不少小伙伴和我一样用github issues记录自己的blog,但是久而久之也发现了一些小问题,比如

    ssh1995
  • 手把手教你开发人工智能微信小程序(4): 训练手写数字识别模型

    在上篇文章《手把手教你开发人工智能微信小程序(3):加载数据》中,我给大家演示了如何通过fetch加载网络数据并进行数据归范化,出于演示的目的,例子做了简化处理...

    云水木石
  • C++中const小结

    1、const修饰普通变量(非指针变量) const修饰变量,一般有两种写法: const TYPE value; TYPE const value; 对于一个...

    用户1215536
  • 初级程序员面试不靠谱指南(二)

    3.read-only的const。如果你突然冒出一句看似很高深的话但又不解释一般都是装逼,就像前面提到过const准确的应该理解为一个read-only的变量...

    一心一怿
  • Dart 中final和const的使用详解 原

    ----final:只能被设一次值,在声明处赋值,值和普通变量的设值一样,可以是对象、字符串、数字等,用于修饰值的表达式不变的变量;

    南郭先生
  • C++雾中风景3:const用法的小结

    const关键字,翻译成中文是常量,常数的意思。所以在绝大多数场合之中,const是来定义常量的,定义常量也是好的编程习惯。在C类语言之中,定义常量通常会使用宏...

    HappenLee

扫码关注云+社区

领取腾讯云代金券