2022-08-24：给定一个长度为3N的数组，其中最多含有0、1、2三种值，你可以把任何一个连续区间上的数组

2022-08-24：给定一个长度为3N的数组，其中最多含有0、1、2三种值，
你可以把任何一个连续区间上的数组，全变成0、1、2中的一种，
目的是让0、1、2三种数字的个数都是N。
返回最小的变化次数。
来自京东。4.2笔试。

答案2022-08-24：

自然智慧即可。统计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;
}