Medium

题目描述

给你一个整数数组 nums 和一个非负整数 k。在一次操作中，你可以将任意一个元素增加或减少 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^5
  • 1 <= nums[i] <= 10^9
  • 1 <= k <= 10^9

解题思路

解题思路

这道题的关键在于理解中位数的性质和贪心策略。

首先需要明确中位数的位置：将数组排序后，中位数位于第 n/2 个位置（从0开始，对于奇数长度数组是正中间，对于偶数长度数组是较大的那个中位数）。

解题的核心思想是：

  1. 排序数组：先将数组按升序排列
  2. 定位中位数：确定中位数在排序后数组中的位置
  3. 贪心调整：
    • 中位数位置必须变为 k
    • 中位数左侧的元素如果大于 k，需要减小到 k（保证中位数是"中间"值）
    • 中位数右侧的元素如果小于 k，需要增大到 k（保证中位数是"中间"值）
    • 其他元素保持不变

这样做的正确性在于：要使中位数为 k，那么中位数左侧至少要有一半元素 ≤ k，右侧至少要有一半元素 ≥ k。贪心地调整违反这个条件的元素到 k 是最优的。

时间复杂度主要来自排序，空间复杂度为排序所需的额外空间。

代码实现

class Solution {
public:
    long long minOperationsToMakeMedianK(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int medianIndex = n / 2;
        long long operations = 0;
        
        // 调整中位数位置的值
        operations += abs(nums[medianIndex] - k);
        
        // 调整中位数左侧大于k的元素
        for (int i = 0; i < medianIndex; i++) {
            if (nums[i] > k) {
                operations += nums[i] - k;
            }
        }
        
        // 调整中位数右侧小于k的元素
        for (int i = medianIndex + 1; i < n; i++) {
            if (nums[i] < k) {
                operations += k - nums[i];
            }
        }
        
        return operations;
    }
};

class Solution:
    def minOperationsToMakeMedianK(self, nums: List[int], k: int) -> int:
        nums.sort()
        n = len(nums)
        median_index = n // 2
        operations = 0
        
        # 调整中位数位置的值
        operations += abs(nums[median_index] - k)
        
        # 调整中位数左侧大于k的元素
        for i in range(median_index):
            if nums[i] > k:
                operations += nums[i] - k
        
        # 调整中位数右侧小于k的元素
        for i in range(median_index + 1, n):
            if nums[i] < k:
                operations += k - nums[i]
        
        return operations

public class Solution {
    public long MinOperationsToMakeMedianK(int[] nums, int k) {
        Array.Sort(nums);
        int n = nums.Length;
        int medianIndex = n / 2;
        long operations = 0;
        
        // 调整中位数位置的值
        operations += Math.Abs(nums[medianIndex] - k);
        
        // 调整中位数左侧大于k的元素
        for (int i = 0; i < medianIndex; i++) {
            if (nums[i] > k) {
                operations += nums[i] - k;
            }
        }
        
        // 调整中位数右侧小于k的元素
        for (int i = medianIndex + 1; i < n; i++) {
            if (nums[i] < k) {
                operations += k - nums[i];
            }
        }
        
        return operations;
    }
}

var minOperationsToMakeMedianK = function(nums, k) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const medianIndex = Math.floor(n / 2);
    let operations = 0;
    
    // 调整中位数位置的值
    operations += Math.abs(nums[medianIndex] - k);
    
    // 调整中位数左侧大于k的元素
    for (let i = 0; i < medianIndex; i++) {
        if (nums[i] > k) {
            operations += nums[i] - k;
        }
    }
    
    // 调整中位数右侧小于k的元素
    for (let i = medianIndex + 1; i < n; i++) {
        if (nums[i] < k) {
            operations += k - nums[i];
        }
    }
    
    return operations;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)主要消耗在排序上，遍历数组的时间为 O(n)
空间复杂度O(1)只使用了常数级别的额外空间（不考虑排序的额外空间）

相关题目