csp信奥赛C高频考点专项训练【滑动窗口】案例2不同值计数问题题目描述给定一个长度为n的正整数数组和一个固定长度为k的滑动窗口窗口从数组的最左端移动到最右端。每次窗口向右滑动一个位置你需要计算并输出每个窗口位置中不同整数的个数。输入描述第一行两个整数n和k1 ≤ k ≤ n ≤10 6 10^6106第二行n个整数表示数组元素每个正整数均不超过 1000输出描述一行整数包含n - k 1个值每个值对应窗口滑动过程中窗口内不同整数的个数用空格分隔样例输入8 3 1 2 1 3 2 1 2 3样例输出2 3 3 3 2 3思路分析用固定大小的滑动窗口统计不同整数的个数。由于数组元素值不超过 1000可以用一个计数数组cnt记录当前窗口内每个值出现的次数并用一个变量diff维护窗口中不同值的个数。初始化先统计前k个元素每遇到一个新值cnt[val] 0则diff然后cnt[val]。滑动窗口每向右移动一位左侧元素离开窗口右侧新元素进入窗口。移除左侧元素cnt[out]--若减为 0 则diff--。加入右侧元素若cnt[in] 0则diff然后cnt[in]。每个窗口的答案就是当前的diff依次输出。时间复杂度O(n)空间复杂度O(1000)完全满足n ≤ 1e6的要求。代码实现#includebits/stdc.husingnamespacestd;intn,k,a[1000010];intcnt[1001];//计数数组值≤1000intmain(){cinnk;for(inti1;in;i)cina[i];intdiff0;//当前窗口不同整数的个数for(inti1;ik;i){//初始化第一个窗口if(cnt[a[i]]0)diff;//新值出现种类数1cnt[a[i]];}coutdiff ;//输出第一个窗口答案for(intik1;in;i){//滑动窗口i为右端点intouta[i-k];//即将离开窗口的左端元素cnt[out]--;if(cnt[out]0)diff--;//该值不再出现种类数-1intina[i];//即将进入窗口的右端元素if(cnt[in]0)diff;//新值出现种类数1cnt[in];coutdiff ;//输出当前窗口答案}return0;}功能分析输入处理读取n、k和数组数组元素限制在 1000 内因此计数数组大小固定为 1001。窗口滑动逻辑每次移动只更新两端元素避免重复统计保证每个元素最多进出窗口一次。答案输出按窗口从左到右的顺序输出每个窗口内不同整数的个数空格分隔。完整信奥赛C普及组CSP-J一等奖通关刷题题单及题解请关注专栏https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转【秘籍汇总】完整csp信奥赛C学习资料1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转https://edu.csdn.net/course/detail/41081 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转4、csp信奥赛冲刺一等奖有效刷题题解信奥赛C普及组CSP-J一等奖通关刷题题单及题解https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转信奥赛C普及组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转5、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}