给定一个长度为3N的数组，其中最多含有0、1、2三种值，
你可以把任何一个连续区间上的数组，全变成0、1、2中的一种，
目的是让0、1、2三种数字的个数都是N。
返回最小的变化次数。
自然智慧即可。统计0,1,2扣去N/3的个数之和。
比如[1,1,1]，1有3个，多了两个；而0和2都是0个，不统计；所以结果是2。
时间复杂度：O(N)。
代码用rust编写。代码如下：
use rand::Rng;
fn main() {
let n: i32 = 8;
let test_time: i32 = 2000;
println!("测试开始");
for _ in 0..test_time {
let m = (rand::thread_rng().gen_range(0, n) + 1) * 3;
let mut arr = random_array(m);
let ans1 = min_times1(&mut arr);
let ans2 = min_times2(&mut arr);
if ans1 != ans2 {
println!("出错了!");
break;
}
}
println!("测试结束");
}
const MAX_VALUE: i32 = 1 << 31 - 1;
// 暴力方法
// 为了验证不会超过2次
fn min_times1(arr: &mut Vec<i32>) -> i32 {
let mut set: Vec<i32> = vec![];
for _ in 0..arr.len() {
set.push(0);
}
for i in 0..arr.len() {
set[i] = arr[i];
}
return process1(&mut set, 0, arr);
}
fn process1(set: &mut Vec<i32>, time: i32, origin: &mut Vec<i32>) -> i32 {
let mut cnt: Vec<i32> = vec![];
for _ in 0..3 {
cnt.push(0);
}
for num in set.iter() {
cnt[*num as usize] += 1;
}
if cnt[0] == cnt[1] && cnt[0] == cnt[2] {
return time;
} else {
if time == 2 {
return 3;
}
let mut ans = MAX_VALUE;
for ll in 0..set.len() as i32 {
for rr in ll..set.len() as i32 {
set1(set, ll, rr, 0);
ans = get_min(ans, process1(set, time + 1, origin));
set1(set, ll, rr, 1);
ans = get_min(ans, process1(set, time + 1, origin));
set1(set, ll, rr, 2);
ans = get_min(ans, process1(set, time + 1, origin));
rollback(set, ll, rr, origin);
}
}
return ans;
}
}
fn set1(set: &mut Vec<i32>, ll: i32, rr: i32, v: i32) {
for i in ll..=rr {
set[i as usize] = v;
}
}
fn rollback(set: &mut Vec<i32>, ll: i32, rr: i32, origin: &mut Vec<i32>) {
for i in ll..=rr {
set[i as usize] = origin[i as usize];
}
}
fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
if a > b {
a
} else {
b
}
}
fn get_min<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
if a < b {
a
} else {
b
}
}
// 正式方法
// 时间复杂度O(N)
fn min_times2(arr: &mut Vec<i32>) -> i32 {
let mut cnt: Vec<i32> = vec![];
for _ in 0..3 {
cnt.push(0);
}
for num in arr.iter() {
cnt[*num as usize] += 1;
}
if cnt[0] == cnt[1] && cnt[0] == cnt[2] {
return 0;
}
let n = arr.len() as i32;
let m = n / 3;
if (cnt[0] < m && cnt[1] < m) || (cnt[0] < m && cnt[2] < m) || (cnt[1] < m && cnt[2] < m) {
return 2;
} else {
// 只有一种数的个数是小于m的
return if once(arr, &mut cnt, m) { 1 } else { 2 };
}
}
// 只有一种数是少于N/3
fn once(arr: &mut Vec<i32>, cnt: &mut Vec<i32>, m: i32) -> bool {
let less_v = if cnt[0] < m {
0
} else {
if cnt[1] < m {
1
} else {
2
}
};
let less_t = if less_v == 0 {
cnt[0]
} else {
if less_v == 1 {
cnt[1]
} else {
cnt[2]
}
};
if cnt[0] > m && modify(arr, 0, cnt[0], less_v, less_t) {
return true;
}
if cnt[1] > m && modify(arr, 1, cnt[1], less_v, less_t) {
return true;
}
if cnt[2] > m && modify(arr, 2, cnt[2], less_v, less_t) {
return true;
}
return false;
}
// 0 -> 10个
// 1 -> 10个
// 2 -> 10个
// ==========
// 0 -> 7个
// 2 -> 12个 1 -> 11个
// 多的数 2
// 少的数 0
fn modify(arr: &mut Vec<i32>, more: i32, more_t: i32, less: i32, less_t: i32) -> bool {
let mut cnt: Vec<i32> = vec![];
for _ in 0..3 {
cnt.push(0);
}
cnt[less as usize] = less_t;
cnt[more as usize] = more_t;
// 目标
let aim = arr.len() as i32 / 3;
let mut ll = 0;
let mut rr = 0;
while rr < arr.len() as i32 || cnt[more as usize] <= aim {
// cnt[more] 窗口之外，多的数有几个？
if cnt[more as usize] > aim {
// R++ 窗口右边界，右移
cnt[arr[rr as usize] as usize] -= 1;
rr += 1;
} else if cnt[more as usize] < aim {
cnt[arr[ll as usize] as usize] += 1;
ll += 1;
} else {
// 在窗口之外，多的数，够了！
// 少的数，和，另一种数other，能不能平均！都是10个！
if cnt[less as usize] + rr - ll < aim {
cnt[arr[rr as usize] as usize] -= 1;
rr += 1;
} else if cnt[less as usize] + rr - ll > aim {
cnt[arr[ll as usize] as usize] += 1;
ll += 1;
} else {
return true;
}
}
}
return false;
}
// 为了测试
fn random_array(len: i32) -> Vec<i32> {
let mut ans: Vec<i32> = vec![];
for _ in 0..len {
ans.push(rand::thread_rng().gen_range(0, 3));
}
return ans;
}执行结果如下：
