小A认为如果在数组中有一个数出现了至少k次，
且这个数是该数组的众数，即出现次数最多的数之一，
那么这个数组被该数所支配，
显然当k比较大的时候，有些数组不被任何数所支配。
现在小A拥有一个长度为n的数组，她想知道内部有多少个区间是被某个数支配的。
2 <= k <= n <= 100000，
1 <= 数组的值 <= n。
窗口问题。
求总数，求不被支配的数量。
时间复杂度：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;
}
