class Solution {
public:
long long makeSubKSumEqual(vector<int>& arr, int k) {
}
};
6329. 使子数组元素和相等
给你一个下标从 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 <= 1051 <= arr[i] <= 109原站题解
golang 解法, 执行用时: 180 ms, 内存消耗: 9.5 MB, 提交时间: 2023-04-02 12:27:37
func makeSubKSumEqual(arr []int, k int) (ans int64) {
k = gcd(k, len(arr))
g := make([][]int, k)
for i, x := range arr {
g[i%k] = append(g[i%k], x)
}
for _, b := range g {
sort.Ints(b)
for _, x := range b {
ans += int64(abs(x - b[len(b)/2]))
}
}
return
}
func gcd(a, b int) int {
for a != 0 {
a, b = b%a, a
}
return b
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
java 解法, 执行用时: 99 ms, 内存消耗: 62.9 MB, 提交时间: 2023-04-02 12:27:23
class Solution {
public long makeSubKSumEqual(int[] arr, int k) {
int n = arr.length;
k = gcd(k, n);
long ans = 0;
for (int i = 0; i < k; ++i) {
var b = new ArrayList<Integer>();
for (int j = i; j < n; j += k)
b.add(arr[j]);
Collections.sort(b);
int mid = b.get(b.size() / 2);
for (int x : b)
ans += Math.abs(x - mid);
}
return ans;
}
private int gcd(int a, int b) {
while (a != 0) {
int tmp = a;
a = b % a;
b = tmp;
}
return b;
}
}
python3 解法, 执行用时: 148 ms, 内存消耗: 31 MB, 提交时间: 2023-04-02 12:27:10
class Solution:
def makeSubKSumEqual(self, arr: List[int], k: int) -> int:
k = gcd(k, len(arr))
ans = 0
for i in range(k):
b = sorted(arr[i::k])
mid = b[len(b) // 2]
ans += sum(abs(x - mid) for x in b)
return ans