leetcode 2592. 最大化数组的伟大值

2592. 最大化数组的伟大值

法一：排序

丑陋的代码

class Solution {
public:
    int maximizeGreatness(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int size = nums.size(),res = 0;
        for(int i = 0,j = 0;i < size && j < size;++i,++j){
            while(j < size){
                if(nums[i] < nums[j]){
                    ++res;break;
                }
                ++j;
            }
        }
        return res;
    }
};

优雅的代码

class Solution {
public:
    int maximizeGreatness(vector<int> &nums) {
        sort(nums.begin(), nums.end());
        int i = 0;
        for (int &x : nums)
            if (nums[i] < x)
                ++i;
        return i;
    }
};

法二：利用两个指针之间的距离

class Solution {
public:
    int maximizeGreatness(vector<int> &nums) {
        int mx = 0;
        unordered_map<int, int> cnt;
        for (int &x : nums)
            mx = max(mx, ++cnt[x]);
        return nums.size() - mx;
    }
};