LeetCode 2607. 使子数组元素和相等 C#
原题链接
中等
作者:
hpstory
,
2023-04-03 11:19:38
,
所有人可见
,
阅读 170
C# 贪心 + 裴蜀定理代码
// 子数组元素和相等
// arr[i] + arr[i + 1] + ... + arr[i + k - 1] == arr[i + 1] + arr[i + 2] + ... + arr[i + k]
// ==> arr[i] == arr[i + k]
// 即将arr分成若干个组,让这些组中数值相等的最小操作数
// 由于有循环存在,可能导致分组错误
// 一个循环数组如果既有周期n,又有周期k,则有周期gcd(n, k)
public class Solution {
public long MakeSubKSumEqual(int[] arr, int k) {
int n = arr.Length;
int x = Gcd(n, k);
long result = 0;
for (int i = 0; i < x; i++){
List<int> group = new List<int>();
for (int j = i; j < n; j += x){
group.Add(arr[j]);
}
group.Sort();
// 中位数是最优选择
int median = group[group.Count / 2];
foreach (int j in group){
result += Math.Abs(median - j);
}
}
return result;
int Gcd(int a, int b){
return b > 0 ? Gcd(b, a % b) : a;
}
}
}
C# 贪心 + 并查集代码
public class Solution {
private int[] p;
private int Find(int x){
if (p[x] != x) p[x] = Find(p[x]);
return p[x];
}
public long MakeSubKSumEqual(int[] arr, int k) {
int n = arr.Length;
this.p = new int[n];
for (int i = 0; i < n; i++) p[i] = i;
for (int i = 0; i < n; i++){
if (Find(i) != Find((i + k) % n)){
p[Find(i)] = Find((i + k) % n);
}
}
Dictionary<int, List<int>> dict = new Dictionary<int, List<int>>();
for (int i = 0; i < n; i++){
int a = Find(i);
if (!dict.ContainsKey(a)) dict.Add(a, new List<int>());
dict[a].Add(arr[i]);
}
long result = 0;
foreach (var kv in dict){
var group = kv.Value;
group.Sort();
int median = group[group.Count / 2];
foreach (int x in group){
result += Math.Abs(median - x);
}
}
return result;
}
}