【贪心算法】力扣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 两种整数。

class Solution {
public:
    int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
        unordered_map<int, int> group;
        for(int num : arr){
            group[num]++;
        }
        vector<pair<int, int>> freq(group.begin(),group.end());
        int ans = freq.size();
        sort(freq.begin(),freq.end(),[](const auto &a,const auto &b){return a.second < b.second;});
        for(auto [_,sb] : freq){
            if(k>=sb){
                ans --;
                k -= sb;
            }else{
                break;
            }
        }
        return ans;
    }
};

先定义一个哈希表group来储存键值对，键是整数，值是该整数的频数。由于哈希表本身没有sort功能，所以将它复制到vector容器中。[](const auto &a,const auto &b){return a.second < b.second;}定义了以freq中的值进行升序排列。for(auto [_,sb] : freq)是结构化绑定，由于我们不需要用到freq的第一个元素，所以用" _ "来表示在结构化绑定中忽略该元素。在结构化绑定中，必须使用方括号 [ ] 而不是花括号 { } 来解构元素。最后进行逻辑运算后返回ans即可。

原文地址：https://blog.csdn.net/sjsjs11/article/details/140516992

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！