2023-02-20：小 A 认为如果在数组中有一个数出现了至少 k 次， 且这个数是该数组的众数，即出现次数最多的数之一， 那么这个数组被该数所支配， 显然当 k 比较大的时候，有些数组不被任何数所支配。 现在

use rand::Rng;use std::collections::HashMap;use std::iter::repeat;fn main() {    let nn = 100;    let test_times = 5000;    println!("测试开始");    for i in 0..test_times {        let n = rand::thread_rng().gen_range(0, nn) + 1;        let mut arr = random_array(n);        let k = rand::thread_rng().gen_range(0, n) + 1;        let ans1 = dominates1(&mut arr, k);        let ans2 = dominates2(&mut arr, k);        if ans1 != ans2 {            println!("出错了!");            return;        }    }    println!("测试结束");}
// 暴力方法// 为了验证// 时间复杂度O(N^3)fn dominates1(arr: &mut Vec<i32>, k: i32) -> i32 {    let n = arr.len() as i32;    let mut ans = 0;    for l in 0..n {        for r in l..n {            if ok(arr, l, r, k) {                ans += 1;            }        }    }    return ans;}
fn ok(arr: &mut Vec<i32>, l: i32, r: i32, k: i32) -> bool {    let mut map: HashMap<i32, i32> = HashMap::new();    for i in l..=r {        if map.contains_key(&arr[i as usize]) {            map.insert(arr[i as usize], map.get(&arr[i as usize]).unwrap() + 1);        } else {            map.insert(arr[i as usize], 1);        }    }    for (_, times) in map.iter() {        if *times >= k {            return true;        }    }    return false;}
// 正式方法// 时间复杂度O(N)fn dominates2(arr: &mut Vec<i32>, k: i32) -> i32 {    let n = arr.len() as i32;    // 总数量    let all = n * (n + 1) / 2;    // 不被支配的区间数量    let mut except = 0;    // 次数表    // 0 : 0    // 1 : 0    // 2 : 0    let mut cnt: Vec<i32> = repeat(0).take((n + 1) as usize).collect();    // l ... r    // 窗口用这个形式[l,r)    // l...r-1 r(x)    // l == 0 r == 0 [l,r) 一个数也没有    // l == 0 r == 1 [0..0]    let mut l = 0;    let mut r = 0;    while l < n {        // [r] 即将要进来的        // cnt[arr[r]] + 1 < k        while r < n && cnt[arr[r as usize] as usize] + 1 < k {            // cnt[arr[r]]++;            // r++            cnt[arr[r as usize] as usize] += 1;            r += 1;        }        // l..l        // l..l+1        // l..l+2        // l..r-1        except += r - l;        cnt[arr[l as usize] as usize] -= 1;        l += 1;    }    return all - except;}
// 为了测试fn random_array(n: i32) -> Vec<i32> {    let mut ans: Vec<i32> = repeat(0).take(n as usize).collect();    for i in 0..n {        ans[i as usize] = rand::thread_rng().gen_range(0, n) + 1;    }    return ans;}