Medium

题目描述

给你一个由正整数组成的数组 nums。

同时给你一个长度为 m 的整数数组 queries。对于第 i 个查询，你想要使 nums 的所有元素都等于 queries[i]。你可以对数组执行以下操作任意次数：

  • 将数组的某个元素增加或减少 1。

返回一个长度为 m 的数组 answer，其中 answer[i] 是使所有 nums 的元素都等于 queries[i] 所需的最少操作数。

注意，每次查询后，数组都会重置为其原始状态。

示例 1：

输入：nums = [3,1,6,8], queries = [1,5]
输出：[14,10]
解释：对于第一个查询，我们可以执行以下操作：
- 将 nums[0] 减少 2 次，使得 nums = [1,1,6,8]。
- 将 nums[2] 减少 5 次，使得 nums = [1,1,1,8]。
- 将 nums[3] 减少 7 次，使得 nums = [1,1,1,1]。
所以第一个查询的总操作数是 2 + 5 + 7 = 14。
对于第二个查询，我们可以执行以下操作：
- 将 nums[0] 增加 2 次，使得 nums = [5,1,6,8]。
- 将 nums[1] 增加 4 次，使得 nums = [5,5,6,8]。
- 将 nums[2] 减少 1 次，使得 nums = [5,5,5,8]。
- 将 nums[3] 减少 3 次，使得 nums = [5,5,5,5]。
所以第二个查询的总操作数是 2 + 4 + 1 + 3 = 10。

示例 2：

输入：nums = [2,9,6,3], queries = [10]
输出：[20]
解释：我们可以将数组中的每个值增加到 10。总操作数为 8 + 1 + 4 + 7 = 20。

约束条件：

  • n == nums.length
  • m == queries.length
  • 1 <= n, m <= 10^5
  • 1 <= nums[i], queries[i] <= 10^9

解题思路

这道题要求计算将数组中所有元素变为目标值所需的最少操作数。

思路分析：

对于每个查询值 q，我们需要计算所有元素与 q 的绝对差值之和。这等价于计算 Σ|nums[i] - q|。

暴力解法： 直接遍历每个查询，对每个元素计算绝对差值并求和。时间复杂度为 O(n×m)，在题目约束下可能超时。

优化解法（推荐）： 使用排序 + 前缀和 + 二分查找

  1. 首先对数组 nums 进行排序
  2. 计算前缀和数组，便于快速计算区间和
  3. 对于每个查询值 q，使用二分查找找到分界点：
    • 小于 q 的元素需要增加到 q
    • 大于等于 q 的元素需要减少到 q
  4. 利用前缀和快速计算两部分的操作数：
    • 左边部分：q × 左边元素个数 - 左边元素和
    • 右边部分：右边元素和 - q × 右边元素个数

这种方法的时间复杂度为 O(n log n + m log n)，空间复杂度为 O(n)。

代码实现

class Solution {
public:
    vector<long long> minOperations(vector<int>& nums, vector<int>& queries) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        
        // 计算前缀和
        vector<long long> prefix(n + 1, 0);
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        
        vector<long long> result;
        for (int q : queries) {
            // 二分查找第一个大于等于q的位置
            int pos = lower_bound(nums.begin(), nums.end(), q) - nums.begin();
            
            long long operations = 0;
            // 左边部分：需要增加到q
            if (pos > 0) {
                operations += (long long)q * pos - prefix[pos];
            }
            // 右边部分：需要减少到q
            if (pos < n) {
                operations += (prefix[n] - prefix[pos]) - (long long)q * (n - pos);
            }
            
            result.push_back(operations);
        }
        
        return result;
    }
};

class Solution:
    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:
        nums.sort()
        n = len(nums)
        
        # 计算前缀和
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + nums[i]
        
        result = []
        for q in queries:
            # 二分查找第一个大于等于q的位置
            pos = bisect.bisect_left(nums, q)
            
            operations = 0
            # 左边部分：需要增加到q
            if pos > 0:
                operations += q * pos - prefix[pos]
            # 右边部分：需要减少到q
            if pos < n:
                operations += (prefix[n] - prefix[pos]) - q * (n - pos)
            
            result.append(operations)
        
        return result

public class Solution {
    public IList<long> MinOperations(int[] nums, int[] queries) {
        Array.Sort(nums);
        int n = nums.Length;
        
        // 计算前缀和
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        
        List<long> result = new List<long>();
        foreach (int q in queries) {
            // 二分查找第一个大于等于q的位置
            int pos = Array.BinarySearch(nums, q);
            if (pos < 0) pos = ~pos;
            
            long operations = 0;
            // 左边部分：需要增加到q
            if (pos > 0) {
                operations += (long)q * pos - prefix[pos];
            }
            // 右边部分：需要减少到q
            if (pos < n) {
                operations += (prefix[n] - prefix[pos]) - (long)q * (n - pos);
            }
            
            result.Add(operations);
        }
        
        return result;
    }
}

var minOperations = function(nums, queries) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    
    // 计算前缀和
    const prefix = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    
    const result = [];
    for (const q of queries) {
        // 二分查找第一个大于等于q的位置
        let left = 0, right = n;
        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            if (nums[mid] < q) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        const pos = left;
        
        let operations = 0;
        // 左边部分：需要增加到q
        if (pos > 0) {
            operations += q * pos - prefix[pos];
        }
        // 右边部分：需要减少到q
        if (pos < n) {
            operations += (prefix[n] - prefix[pos]) - q * (n - pos);
        }
        
        result.push(operations);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n log n + m log n)
空间复杂度O(n)

其中 n 是数组 nums 的长度，m 是查询数组的长度。排序需要 O(n log n)，每次查询的二分查找需要 O(log n)。

相关题目