这道题本身比较难，需要掌握裴蜀定理。
我今天想到的优化就是把原先数组排序找中位数，直接变成只寻找中位数（利用最近学到的寻找kth大的数来解决，随机选择的思想），优化找中位数的这一步的时间复杂度（时间复杂度这一步做到O(N),N不是原数组的大小，而是temp数组的大小）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Solution {
public long makeSubKSumEqual(int[] arr, int k) {
// 周期k,n 周期gcd(n, k)
int n = arr.length;
long ans = 0;
k = gcd(n, k);
for (int i = 0;i < k;i++) {
//List<Integer> list = new ArrayList<>();
int[] temp = new int[n / k];
int groupSize = 0;
for (int j = i;j < n;j += k) {
temp[groupSize++] = arr[j];
}
// int size = list.size();
int m = findKth(temp, 0, groupSize - 1 , groupSize / 2);
for (int j = i;j < n;j += k) {
ans += Math.abs((long) m - (long) arr[j]);
}
}
return ans;
}
public int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
public int first, last;
public int findKth(int[] arr,int l, int r, int i) {
if (l >= r) return arr[l];
int m = arr[l + (int)(Math.random() * (r - l + 1))];
partition(arr, l, r, m);
if (i < first) {
return findKth(arr, l, first - 1, i);
} else if (i > last) {
return findKth(arr, last + 1, r, i);
} else {
return arr[i];
}
}
public void partition(int[] arr, int l, int r, int m) {
first = l;
last = r;
int i = l;
while (i <= last) {
if (arr[i] == m) {
i++;
} else if (arr[i] < m) {
swap(arr, first++, i++);
} else {
swap(arr, last--, i);
}
}
}
public void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
