Leetcode---376周赛---中位数贪心

题目列表

2965. 找出缺失和重复的数字

2966. 划分数组并满足最大差限制

2967. 使数组成为等数数组的最小代价

2968. 执行操作使频率分数最大

一、找到缺失和重复的数字

由于数据范围不是很大，可以直接暴力统计每个数字出现的次数，时间复杂度为O(n^2)

class Solution {
public:
    vector<int> findMissingAndRepeatedValues(vector<vector<int>>& grid) {
        vector<int>ans(2);
        int n=grid.size();
        vector<int>cnt(n*n+1);
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                cnt[grid[i][j]]++;
            }
        }

        for(int i=1;i<=n*n;i++){
            if(cnt[i]==2){
                ans[0]=i;
            }else if(cnt[i]==0){
                ans[1]=i;
            }
        }
        return ans;
    }
};

二、划分数组并满足最大差限度

这题题目说的不是很清楚，这里的"子数组"不要求连续，即与数字的顺序无关(可以看示例)，所以我们可以直接排序，?然后找元素的最大最小值，简单模拟一下

class Solution {
public:
    vector<vector<int>> divideArray(vector<int>& nums, int k) {
        vector<vector<int>>ans;
        int n=nums.size();
        sort(nums.begin(),nums.end());
        for(int i=0;i<n;i+=3){
            if(nums[i+2]-nums[i]<=k)
                ans.push_back({nums[i],nums[i+1],nums[i+2]});
            else
                return {};
        }
        return ans;
    }
};

三、使数组成为等数数组的最小代价

这题的难点有两个：

1、回文数怎么处理？

2、抛开回文数，只看x，我们该如何选择x让它的代价尽可能的小？

问题1：回文数，要求左右数字对应相等，即我们只要枚举它的前半部分然后对称过去，就能得到一个回文数，我们这里选择先预处理得到数据范围内的所有回文串，具体看代码

问题2：如何选择x？这里是中位数贪心的思想，即x选择数组中的中位数最好。为什么？

结合上面两个问题的思路，我们来看看该如何写？首先我们有所有的回文数，然后我们通过中位数贪心知道，我们选择的回文数要尽可能的在中间位置，可以用二分找到附近的回文串，进行比较，找到最符合条件的

//预处理
vector<int>v;
int init=[](){
    for(int i=1;i<=10000;i*=10){//枚举回文串的前缀
        for(int j=i;j<i*10;j++){
            int x=j/10;
            int y=j;
            while(x){
                y=y*10+x%10;
                x/=10;
            }
            v.push_back(y);    
        }

        if(i<=1000){//i==10000会超范围，比如 12345 54321 数量级为1e9
            for(int j=i;j<i*10;j++){
                int x=j;
                int y=j;
                while(x){
                    y=y*10+x%10;
                    x/=10;
                }
                v.push_back(y);    
            }
        }
    }
    v.push_back(1000000001);//方便后面计算
    return 0;
}();

class Solution {
public:
    long long minimumCost(vector<int>& nums) {
        sort(nums.begin(),nums.end());//中位数贪心一定要先排序
        int n=nums.size();
        auto cost=[&](int x)->long long{
            long long s=0;
            for(int i=0;i<n;i++)
                s+=abs(x-nums[i]);
            return s;
        };
        //找中位数附近的回文串，如果n为奇数，nums[(n-1)/2]为正中间那个数，如果n为偶数，nums[(n-1)/2]为中间两个数的左边那个
        int i=lower_bound(v.begin(),v.end(),nums[(n-1)/2])-v.begin();

        //如果n为奇数，不成立(因为(n-1)/2==n/2)，得找前面的回文数和它比较
        //如果n为偶数，则nums[n/2]为中间两个数的右边那个，即v[i]在两个数之间，正好符合中位数贪心，直接放回
        if(nums[n/2]>=v[i])
            return cost(v[i]);
        //否则需要比较
        return min(cost(v[i]),cost(v[i-1]));
    }
};

四、执行操作使频率分数最大

这题其实也和中位数贪心有关。为了让一个数成为出现次数最大的众数，那么我们操作的这些数肯定是相邻的，因为它们本身就很接近，这样我们将单一数字变成我们希望的众数的操作次数才会尽可能的少，才能有更多的操作次数让其他的数更有可能变成我们想要的众数，增加众数的频率。

那么选择什么数作为众数比较好呢？

如果我们选择了一些连续的数字进行操作，那么根据中位数贪心的原理，我们选择的众数最好是这些数字的中位数，这样其它数字到它的距离之和才会是最小的，也就是操作次数最少。如果操作次数>k，就需要去掉一些数，如果操作次数<=k，就增加一些数，很明显的滑动窗口

代码如下

class Solution {
    typedef long long LL;
public:
    int maxFrequencyScore(vector<int>& nums, long long k) {
        sort(nums.begin(),nums.end());
        int ans=0;
        int n=nums.size();
        vector<LL>pre(n+1);
        for(int i=0;i<n;i++)
            pre[i+1]=pre[i]+nums[i];
        function<LL(LL,LL)>check=[&](LL l,LL r)->LL{
            LL mid=(l+r)/2;//这里的中位数下标要算对
            LL left=(mid-l)*nums[mid]-(pre[mid]-pre[l]);//中位数左边的数需要的操作数
            LL right=pre[r+1]-pre[mid+1]-(r-mid)*nums[mid];//中位数右边的数需要的操作数
            return left+right;
        };

        for(int l=0,r=0;r<n;r++){
            while(check(l,r)>k)
                l++;
            ans=max(ans,r-l+1);
        }
        return ans;
    }
};