专栏：50多种数据结构彻底征服

专栏：50多种经典图论算法全部掌握

最近小红书取消大小周的事上了热搜，按说这是好事，可是偏偏有些人不喜欢，说取消大小周，工资少了15%，宁愿周六加班，结果文章一发，评论区就被网友狂怼。

双休是全人类一直都在追求的，也是当年很多西方国家通过罢工流血得来的，我觉得双休才是更加符合工作和休息相平衡的一种生活方式。喜欢加班自己去加就好了，小红书又没说禁止加班。

加班就是内卷 ，其实我不反对自愿加班，但我反对强制加班。取消大小周，想加班的自己去加就行了，因为确实有不少人挣钱的欲望非常强烈，尤其是单身还没成家的，一个人在出租屋里实在是无聊，想去加班挣钱也未尝不可。但如果非要带上大家一起加班就很不合理了。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第1481题：不同整数的最少数目，难度是中等。

给你一个整数数组 arr 和一个整数 k 。现需要从数组中恰好移除 k 个元素，请找出移除后数组中不同整数的最少数目。

示例1：

输入：arr = [5,5,4], k = 1 输出：1 解释：移除 1 个 4 ，数组中只剩下 5 一种整数。

示例2：

输入：arr = [4,3,1,1,3,3,2], k = 3 输出：2 解释：先移除 4、2 ，然后再移除两个 1 中的任意 1 个或者三个 3 中的任意 1 个，最后剩下 1 和 3 两种整数。

  • 1 <= arr.length <= 10^5

  • 1 <= arr[i] <= 10^9

  • 0 <= k <= arr.length

问题分析

这题说的是从数组中移除 k 个元素，使数组中剩余元素不同的数目最少。既然要不同元素的数目最少，我们只需移除出现频率最少的元素即可。比如数组[1,2,3,3,4,4,4]，k 为 2，移除 1 和 2 ，数组中剩余不同元素只有 3 和 4 ，数量最少。

所以我们可以通过map先统计每个元素出现的频率，然后再根据频率从小到大排序，最后在移除频率最小的 k 个元素即可。移除的时候要注意，最后一个元素有可能没有完全移除，比如[1,2,2,2,4,4,4,4]，k=3，我们可以移除 1 和 2 ，但 2 没有被全部移除，还剩下一个。

JAVA：

// 对频率进行排序 public int findLeastNumOfUniqueInts(int[] arr, int k) {     // 统计每个元素出现的频率     Map mp =  new HashMap<>();     for (int num : arr)         mp.put(num, mp.getOrDefault(num, 0) + 1);     // 把map中的元素转化为数组。     int size = mp.size();     int[][] nums = newint[size][];     int i = 0;     for (Map.Entry entry : mp.entrySet())         nums[i++] = newint[]{entry.getKey(), entry.getValue()};     Arrays.sort(nums, Comparator.comparingInt(o -> o[1]));// 根据频率进行排序     i = 0;     while (k > 0) {         k -= nums[i++][1];         if (k < 0) {             i--;// 第 i 个元素没有完全移除。             break;         }     }     return size - i; }

C++：

public:     int findLeastNumOfUniqueInts(vector

 &arr, int k) {         // 统计每个元素出现的频率         unordered_map

 mp;         for (int num: arr)             mp[num]++;         // 把map中的元素转化为数组。         vector int ,  int >> nums;          for  ( const auto  &entry: mp)             nums.emplace_back(entry.first, entry.second);          // 根据频率进行排序         sort(nums.begin(), nums.end(), []( const auto  &a,  const auto  &b) {              return  a.second < b.second;         });          int  i =  0 ;          while  (k >  0 ) {             k -= nums[i++].second;              if  (k <  0 ) {                 i--; // 第 i 个元素没有完全移除。                  break ;             }         }          return  nums.size() - i;     }

笔者简介

博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。