中位数贪心

题目1

题目链接

462. 最小操作次数使数组元素相等 II - 力扣（LeetCode）

题目大意

给你一个长度为 n 的整数数组 nums ，返回使所有数组元素相等需要的最小操作数。

在一次操作中，你可以使数组中的一个元素加 1 或者减 1 。

示例

输入：nums = [1,2,3]
输出：2
解释：
只需要两次操作（每次操作指南使一个元素加 1 或减 1）：
[1,2,3]  =>  [2,2,3]  =>  [2,2,2]

思路

此处证明为何将所有数变成中位数的操作次数是最少的？

绝对值不等式

∣a∣+∣b∣+∣c∣+⋯+∣z∣≥∣a+b+c+⋯+z∣ （当且仅当 \(a >= 0\),\(b >= 0\) ,\(c>=0\),...\(z >= 0\),等号成立）

证明

设一个长度为 \(n\) 的数组 \(A\)，经过调整后所有的元素都等于 \(x\)​，

\(ans = |x - A_1| + |x - A_2| + ... + |x - A_k| + |x - A_{k + 1}| + ... + |x - A_{2k - 1}| + |x - A_{2k}|\) + ...

①假设，\(n\) 为偶数。

\(ans = |x - A_1| + |x - A_2| + ... + |x - A_k| + |A_{k + 1} - x| + ... + |A_{2k - 1} - x| + |A_{2k} - x|\) >= \(|-A_1 - A_2 - ... - A_k + A_{k + 1} + ... +A_{2k}|\)

当且仅当，有一半数大于等于 \(x\)，有一半数小于等于 \(x\)。【中位数恰好满足这个条件】

②假设，\(n\)为奇数。

\(ans=|x - A_1| + |x - A_2| + ... + |x - A_k| + |x - A_{k + 1}| + ... + |x - A_{2k - 1}| + |x - A_{2k}| + |x - A_{2k + 1}|\)

进一步转换

\(ans = \frac{1}{2} (2|x-A_1| + ... + 2|x - A_k| + |x - A_{k + 1}| + |A_{k + 1} - x| + ... + 2|A_{2k}| +2|A_{2k + 1}| )\) >= \(\frac{1}{2}|-2A_1 - ... - 2A_k + ... + 2A_{k + 2} + ... + 2A_{2k + 1}|\)

当且仅当,\(x = A_{k + 1}\)时，等号成立！【恰好为中位数】

综上，得证！

代码

！！！！略略略！！！！

题目2

题目链接

2607. 使子数组元素和相等 - 力扣（LeetCode）

题目大意

给你一个下标从 0 开始的整数数组 arr 和一个整数 k 。数组 arr 是一个循环数组。

换句话说，数组中的最后一个元素的下一个元素是数组中的第一个元素，数组中第一个元素的前一个元素是数组中的最后一个元素。

你可以执行下述运算任意次：

• 选中 arr 中任意一个元素，并使其值加上 1 或减去 1 。

执行运算使每个长度为 k 的 子数组 的元素总和都相等，返回所需要的最少运算次数。

子数组 是数组的一个连续部分。

示例

输入：arr = [1,4,1,3], k = 2
输出：1
解释：在下标为 1 的元素那里执行一次运算，使其等于3 。
执行运算后，数组变为 [1,3,1,3] 。
- 0 处起始的子数组为 [1, 3] ，元素总和为 4 
- 1 处起始的子数组为 [3, 1] ，元素总和为 4 
- 2 处起始的子数组为 [1, 3] ，元素总和为 4 
- 3 处起始的子数组为 [3, 1] ，元素总和为 4 

思路

①思考不是循环数组的情况

由 \(a[i]+a[i+1]+⋯+a[i+k−1]=a[i+1]+a[i+2]+⋯+a[i+k]\),得 \(a[i] = a[i + k]\)

由此，只需将\(a[i],a[i + k],a[i + 2k],a[i + 3k]，...\) 变成相同的即可，由上面已经得知，变成中位数是最小的操作！

②思考是循环数组的情况

加上这种情况后，会有什么不同呢？

比如，\(n = 6,k = 4\)

$ a[0],a[4],a[8],a[12],a[16]$ 要相等

但n最大为6【\(a[8],a[12],a[16]\)是不存在的】，也就是说如果超出的话，要从尾部循环到头部

我们来看一下,$ a[8] = a[2],a[12] = a[0],a[16] = a[4]$

所以，\(a[0],a[2],a[4]\)要相等，那么我们的分组就会与不是循环数组的时候可能会多一些！

那么，我们是否可以这样理解？

对于循环数组a，它既有周期 \(6\) ,又有周期 \(4\) ，那么，必然有周期 $ gcd(6,4) = 2$

由裴蜀定理： \(a[i] = a[i + nx + ky] = a[i + gcd(n,k)]\)

代码

class Solution {
public:
    long long makeSubKSumEqual(vector<int> &arr, int k) {
        int n = arr.size();
        int c = gcd(k, n);
        vector<vector<int>> g(c);
        for (int i = 0; i < n; ++i)
            g[i % c].push_back(arr[i]);

        long long ans = 0;
        for (auto &a: g) {
            // 如果仅仅是找第k大的元素的话，那么使用快速选择就可以O(n)的时间复杂度找到，这里以后要记得！
            nth_element(a.begin(), a.begin() + a.size() / 2, a.end());
            for (int x: a)
                ans += abs(x - a[a.size() / 2]);
        }
        return ans;
    }
};

关于中位数的冷知识

如何动态求一个数的中位数？

方法一：find_kth()

方法二：对顶堆【维护一个大顶堆与一个小顶堆】