Medium

题目描述

给你一个下标从 0 开始的整数数组 arr 和一个整数 k。数组 arr 是 环形 的。也就是说，数组的第一个元素是最后一个元素的下一个元素，数组的最后一个元素是第一个元素的前一个元素。

你可以执行下述运算任意次：

  • 选中 arr 中任意一个元素，并使其值加 1 或减 1 。

返回使数组中每个长度为 k 的 子数组 的和相等所需的 最少运算次数 。

子数组 是数组的一个连续部分。

示例 1：

输入：arr = [1,4,1,3], k = 2
输出：1
解释：我们可以在下标 1 执行一次运算，使其等于 3 。
运算后，数组变为 [1,3,1,3]
- 下标 0 处开始的子数组为 [1, 3] ，和为 4
- 下标 1 处开始的子数组为 [3, 1] ，和为 4
- 下标 2 处开始的子数组为 [1, 3] ，和为 4
- 下标 3 处开始的子数组为 [3, 1] ，和为 4

示例 2：

输入：arr = [2,5,5,7], k = 3
输出：5
解释：我们可以在下标 0 执行三次运算使其等于 5，在下标 3 执行两次运算使其等于 5 。
运算后，数组变为 [5,5,5,5]
- 下标 0 处开始的子数组为 [5, 5, 5] ，和为 15
- 下标 1 处开始的子数组为 [5, 5, 5] ，和为 15
- 下标 2 处开始的子数组为 [5, 5, 5] ，和为 15
- 下标 3 处开始的子数组为 [5, 5, 5] ，和为 15

提示：

  • 1 <= k <= arr.length <= 10^5
  • 1 <= arr[i] <= 10^9

解题思路

这道题的核心在于理解环形数组中子数组和相等的约束条件。

关键观察： 当所有长度为 k 的子数组和相等时，相邻子数组的和相等意味着：

  • arr[0] + arr[1] + ... + arr[k-1] = arr[1] + arr[2] + ... + arr[k]
  • 这推导出 arr[0] = arr[k]
  • 同理，arr[1] = arr[k+1]，以此类推

由于数组是环形的，我们可以得出：对于任意下标 i，都有 arr[i] = arr[(i + k) % n]。

数学分析： 如果 gcd(n, k) = g，那么数组会被分成 g 个独立的组，每组内的所有元素必须相等：

  • 第 0 组：下标为 0, g, 2g, 3g, …
  • 第 1 组：下标为 1, 1+g, 1+2g, 1+3g, …
  • …
  • 第 g-1 组：下标为 g-1, g-1+g, g-1+2g, …

解决方案：

  1. 计算 g = gcd(n, k)
  2. 将数组元素按照下标模 g 分组
  3. 对每组内的元素，找到中位数作为目标值
  4. 计算每组内所有元素变为中位数所需的操作次数
  5. 累加所有组的操作次数

选择中位数作为目标值是因为它能最小化绝对差的和。

代码实现

class Solution {
public:
    long long makeSubKSumEqual(vector<int>& arr, int k) {
        int n = arr.size();
        int g = __gcd(n, k);
        
        long long result = 0;
        
        for (int i = 0; i < g; i++) {
            vector<int> group;
            for (int j = i; j < n; j += g) {
                group.push_back(arr[j]);
            }
            
            sort(group.begin(), group.end());
            int median = group[group.size() / 2];
            
            for (int val : group) {
                result += abs(val - median);
            }
        }
        
        return result;
    }
};

class Solution:
    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:
        import math
        
        n = len(arr)
        g = math.gcd(n, k)
        
        result = 0
        
        for i in range(g):
            group = []
            j = i
            while j < n:
                group.append(arr[j])
                j += g
            
            group.sort()
            median = group[len(group) // 2]
            
            for val in group:
                result += abs(val - median)
        
        return result

public class Solution {
    public long MakeSubKSumEqual(int[] arr, int k) {
        int n = arr.Length;
        int g = GCD(n, k);
        
        long result = 0;
        
        for (int i = 0; i < g; i++) {
            List<int> group = new List<int>();
            for (int j = i; j < n; j += g) {
                group.Add(arr[j]);
            }
            
            group.Sort();
            int median = group[group.Count / 2];
            
            foreach (int val in group) {
                result += Math.Abs(val - median);
            }
        }
        
        return result;
    }
    
    private int GCD(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

var makeSubKSumEqual = function(arr, k) {
    const n = arr.length;
    const g = gcd(n, k);
    
    let result = 0;
    
    for (let i = 0; i < g; i++) {
        const group = [];
        for (let j = i; j < n; j += g) {
            group.push(arr[j]);
        }
        
        group.sort((a, b) => a - b);
        const median = group[Math.floor(group.length / 2)];
        
        for (const val of group) {
            result += Math.abs(val - median);
        }
    }
    
    return result;
};

function gcd(a, b) {
    while (b !== 0) {
        [a, b] = [b, a % b];
    }
    return a;
}
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n log n)，主要来自对每个组进行排序
空间复杂度O(n)，用于存储分组的元素

相关题目