Hard
题目描述
给定一个整数数组 nums 和一个整数 k。
在一次操作中，你可以将 nums 的任何元素增加或减少恰好 k。
还给定一个二维整数数组 queries，其中每个 queries[i] = [li, ri]。
对于每个查询，找到使子数组 nums[li..ri] 中所有元素相等所需的最小操作次数。如果不可能，则该查询的答案为 -1。
返回一个数组 ans，其中 ans[i] 是第 i 个查询的答案。
示例 1：
输入：nums = [1,4,7], k = 3, queries = [[0,1],[0,2]]
输出：[1,2]
示例 2：
输入：nums = [1,2,4], k = 2, queries = [[0,2],[0,0],[1,2]]
输出：[-1,0,1]
约束条件：
- 1 <= n == nums.length <= 4 × 10^4
- 1 <= nums[i] <= 10^9
- 1 <= k <= 10^9
- 1 <= queries.length <= 4 × 10^4
- queries[i] = [li, ri]
- 0 <= li <= ri <= n - 1
解题思路
这道题目的关键洞察是：为了使子数组中的所有元素相等，它们必须具有相同的除以k的余数。也就是说，如果 nums[i] % k != nums[j] % k，那么无论进行多少次操作都无法使它们相等。
核心思路：
余数检查：首先检查子数组中所有元素对k的余数是否相同，如果不同则返回-1。
转换问题：将每个元素除以k得到商，问题转化为使所有商相等的最小操作次数。
中位数策略：要使所有数字相等且操作次数最少，最优策略是将所有数字都变为中位数。这是因为中位数能最小化绝对偏差的总和。
计算操作次数：对于每个元素，操作次数等于其与中位数的差的绝对值。
算法步骤：
- 对于每个查询，提取子数组
- 检查所有元素的余数是否相同
- 将元素除以k得到商数组
- 找到商数组的中位数
- 计算所有元素到中位数的距离之和
时间复杂度主要取决于排序操作，对于每个查询需要O(n log n)的时间。
代码实现
class Solution {
public:
vector<long long> minOperations(vector<int>& nums, int k, vector<vector<int>>& queries) {
vector<long long> result;
for (auto& query : queries) {
int left = query[0], right = query[1];
// Extract subarray
vector<long long> subarray;
for (int i = left; i <= right; i++) {
subarray.push_back(nums[i]);
}
// Check if all elements have same remainder
long long remainder = subarray[0] % k;
bool possible = true;
for (long long num : subarray) {
if (num % k != remainder) {
possible = false;
break;
}
}
if (!possible) {
result.push_back(-1);
continue;
}
// Convert to quotients
for (long long& num : subarray) {
num /= k;
}
// Sort to find median
sort(subarray.begin(), subarray.end());
// Find median
int n = subarray.size();
long long median = subarray[n / 2];
// Calculate total operations
long long operations = 0;
for (long long quotient : subarray) {
operations += abs(quotient - median);
}
result.push_back(operations);
}
return result;
}
};
class Solution:
def minOperations(self, nums: List[int], k: int, queries: List[List[int]]) -> List[int]:
result = []
for left, right in queries:
# Extract subarray
subarray = nums[left:right+1]
# Check if all elements have same remainder
remainder = subarray[0] % k
if not all(num % k == remainder for num in subarray):
result.append(-1)
continue
# Convert to quotients
quotients = [num // k for num in subarray]
# Sort to find median
quotients.sort()
# Find median
n = len(quotients)
median = quotients[n // 2]
# Calculate total operations
operations = sum(abs(quotient - median) for quotient in quotients)
result.append(operations)
return result
public class Solution {
public long[] MinOperations(int[] nums, int k, int[][] queries) {
long[] result = new long[queries.Length];
for (int q = 0; q < queries.Length; q++) {
int left = queries[q][0], right = queries[q][1];
// Extract subarray
List<long> subarray = new List<long>();
for (int i = left; i <= right; i++) {
subarray.Add(nums[i]);
}
// Check if all elements have same remainder
long remainder = subarray[0] % k;
bool possible = true;
foreach (long num in subarray) {
if (num % k != remainder) {
possible = false;
break;
}
}
if (!possible) {
result[q] = -1;
continue;
}
// Convert to quotients
for (int i = 0; i < subarray.Count; i++) {
subarray[i] /= k;
}
// Sort to find median
subarray.Sort();
// Find median
int n = subarray.Count;
long median = subarray[n / 2];
// Calculate total operations
long operations = 0;
foreach (long quotient in subarray) {
operations += Math.Abs(quotient - median);
}
result[q] = operations;
}
return result;
}
}
/**
* @param {number[]} nums
* @param {number} k
* @param {number[][]} queries
* @return {number[]}
*/
var minOperations = function(nums, k, queries) {
const result = [];
for (const [l, r] of queries) {
const subarray = nums.slice(l, r + 1);
// Check if all elements have the same remainder when divided by k
const remainder = subarray[0] % k;
let possible = true;
for (let i = 1; i < subarray.length; i++) {
if (subarray[i] % k !== remainder) {
possible = false;
break;
}
}
if (!possible) {
result.push(-1);
continue;
}
if (subarray.length === 1) {
result.push(0);
continue;
}
// Find the median target value
const sortedValues = subarray.map(x => Math.floor(x / k)).sort((a, b) => a - b);
const median = sortedValues[Math.floor(sortedValues.length / 2)];
const target = median * k + remainder;
// Calculate operations needed
let operations = 0;
for (const num of subarray) {
operations += Math.abs(num - target) / k;
}
result.push(operations);
}
return result;
};
复杂度分析
| 复杂度类型 | 值 | 说明 |
|---|---|---|
| 时间复杂度 | O(Q × N log N) | Q为查询数量，N为子数组平均长度，主要消耗在排序上 |
| 空间复杂度 | O(N) | 需要额外空间存储子数组和商数组 |