2023-02-20：小A认为如果在数组中有一个数出现了至少k次， 且这个数是该数组的众数，即出现次数最多的

2023-02-20：小A认为如果在数组中有一个数出现了至少k次，
且这个数是该数组的众数，即出现次数最多的数之一，
那么这个数组被该数所支配，
显然当k比较大的时候，有些数组不被任何数所支配。
现在小A拥有一个长度为n的数组，她想知道内部有多少个区间是被某个数支配的。
2 <= k <= n <= 100000，
1 <= 数组的值 <= n。
来自小红书。

答案2023-02-20：

窗口问题。
求总数，求不被支配的数量。
时间复杂度：O(N)。
空间复杂度：O(N)。

代码用rust编写。代码如下：

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;
}

本作品采用《CC 协议》，转载必须注明作者和本文链接