How can I minimize the operations to make the median equal to k?

Minimize operations by sorting the array and applying a greedy approach to adjust only the elements that affect the median value.

What is the key pattern in the 'Minimum Operations to Make Median of Array Equal to K' problem?

The problem follows a greedy approach where you focus on the median and adjust elements accordingly while maintaining a sorted order.

Does sorting the array always guarantee a solution?

Yes, sorting the array ensures that you can access the median directly and apply operations to only the relevant elements.

What if the array has an even length?

If the array has an even length, the larger of the two middle elements is chosen as the median, which must also be adjusted to k.

What is the time complexity of the solution?

The time complexity is O(n log n) due to the sorting step, followed by a linear scan to apply operations to the median.

#3107

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

使数组中位数等于 K 的最少操作数

给你一个整数数组 nums 和一个非负整数 k 。一次操作中，你可以选择任一元素加 1 或者减 1 。请你返回将 nums 中位数变为 k 所需要的最少操作次数。一个数组的中位数指的是数组按非递减顺序排序后最中间的元素。如果数组长度为偶数，我们选择中间两个数的较大值为中位数。示例 …

数组贪心排序

题目描述

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

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

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

示例 1：

输入：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] 。

示例 3：

输入：nums = [1,2,3,4,5,6], k = 4

输出：0

解释：数组中位数已经等于 k 了。

提示：

1 <= nums.length <= 2 * 10⁵
1 <= nums[i] <= 10⁹
1 <= k <= 10⁹

lightbulb

解题思路

方法一：贪心 + 排序

我们首先对数组 $nums$ 进行排序，然后找到中位数的位置 $m$ ，那么初始时我们需要的操作次数就是 $|nums[m] - k|$ 。

接下来，我们分情况讨论：

如果 $nums[m] \gt k$ ，那么 $m$ 右侧的元素都大于等于 $k$ ，我们只需要将 $m$ 左侧的元素中，大于 $k$ 的元素减小到 $k$ 即可。
如果 $nums[m] \le k$ ，那么 $m$ 左侧的元素都小于等于 $k$ ，我们只需要将 $m$ 右侧的元素中，小于 $k$ 的元素增大到 $k$ 即可。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 是数组 $nums$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def minOperationsToMakeMedianK(self, nums: List[int], k: int) -> int:
        nums.sort()
        n = len(nums)
        m = n >> 1
        ans = abs(nums[m] - k)
        if nums[m] > k:
            for i in range(m - 1, -1, -1):
                if nums[i] <= k:
                    break
                ans += nums[i] - k
        else:
            for i in range(m + 1, n):
                if nums[i] >= k:
                    break
                ans += k - nums[i]
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate correctly identifies the importance of sorting the array before operating on it.
question_mark
Candidate may struggle with the details of greedy selection for the median.
question_mark
Check if the candidate is comfortable with modifying array elements while maintaining order.

warning

常见陷阱

外企场景

error
Not sorting the array first, leading to incorrect identification of the median.
error
Applying operations to elements not affecting the median.
error
Failing to account for the two possible middle elements in arrays with an even length.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Array with an even length where the median is ambiguous.
arrow_right_alt
Test cases with very large values for k and nums[i].
arrow_right_alt
Arrays that are already sorted, testing the candidate's optimization skills.

help

常见问题

外企场景

继续练习

#3111 覆盖所有点的最少矩形数目 #3075 幸福值最大化的选择方案 #3074 重新分装苹果