專欄：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算法文檔 。