题目描述
给你一个整数数组 nums
和一个 非负 整数 k
。
一次操作中,你可以选择任一下标 i
,然后将 nums[i]
加 1
或者减 1
。
请你返回将 nums
中位数 变为 k
所需要的 最少 操作次数。
一个数组的 中位数 指的是数组按 非递减 顺序排序后最中间的元素。如果数组长度为偶数,我们选择中间两个数的较大值为中位数。
样例
输入:nums = [2,5,6,8,5], k = 4
输出:2
解释:我们将 nums[1] 和 nums[4] 减 1 得到 [2, 4, 6, 8, 4]。
现在数组的中位数等于 k。所以答案为 2。
输入:nums = [2,5,6,8,5], k = 7
输出:3
解释:我们将 nums[1] 增加 1 两次,并且将 nums[2] 增加 1 一次,得到 [2, 7, 7, 8, 5]。
结果数组的中位数等于 k。所以答案为 3。
输入:nums = [1,2,3,4,5,6], k = 4
输出:0
解释:数组中位数已经等于 k 了,所以不需要进行任何操作。
限制
1 <= nums.length <= 2 * 10^5
1 <= nums[i] <= 10^9
1 <= k <= 10^9
算法
(贪心,排序) $O(n \log n)$
- 将给定的数组从小到大排序。
- 注意到,将原来的中位数修改为 $k$ 的总代价是最小的,不然的话,可以通过交换两个原始数组的目标值来达到更小的总代价。
- 修改中位数左侧的数字至多为 $k$,修改中位数右侧的数字至少为 $k$。
时间复杂度
- 排序的时间复杂度为 $O(n \log n)$。
- 排序后,遍历数组一次。
- 故总时间复杂度为 $O(n \log n)$。
空间复杂度
- 需要 $O(\log n)$ 的额外空间存储排序的系统栈。
C++ 代码
#define LL long long
class Solution {
public:
LL minOperationsToMakeMedianK(vector<int>& nums, int k) {
const int n = nums.size();
sort(nums.begin(), nums.end());
LL ans = abs(nums[n / 2] - k);
for (int i = 0; i < n / 2; i++)
ans += max(0, nums[i] - k);
for (int i = n / 2 + 1; i < n; i++)
ans += max(0, k - nums[i]);
return ans;
}
};