3107：使数组中位数等于 K 的最少操作数（1604 分）

力扣第 392 场周赛第 3 题

题目

给你一个整数数组 nums 和一个 非负 整数 k 。一次操作中，你可以选择任一元素 加 1 或者减 1 。

请你返回将 nums 中位数 变为 k 所需要的 最少 操作次数。

一个数组的中位数指的是数组按非递减顺序排序后最中间的元素。如果数组长度为偶数，我们选择中间两个数的较大值为中位数。

示例 1：

示例 2：

示例 3：

提示：

• 1 <= nums.length <= 2 * 105
• 1 <= nums[i] <= 109
• 1 <= k <= 109

相似问题：

• 0295：数据流的中位数
• 0480：滑动窗口中位数

分析

排序后，定位中位数下标 m，将前面的数变为<=k，后面的数变为>=k即可。

解答

1
2
3
4
5

class Solution:
    def minOperationsToMakeMedianK(self, nums: List[int], k: int) -> int:
        A = sorted(nums)
        m = len(A)//2
        return sum(max(0,a-k) for a in A[:m+1])+sum(max(0,k-a) for a in A[m:])

193 ms