csp信奥赛C++高频考点专项训练：【滑动窗口】案例2：不同值计数问题

csp信奥赛C++高频考点专项训练：【滑动窗口】案例2：不同值计数问题

题目描述

给定一个长度为n的正整数数组和一个固定长度为k的滑动窗口，窗口从数组的最左端移动到最右端。每次窗口向右滑动一个位置，你需要计算并输出每个窗口位置中不同整数的个数。

输入描述

• 第一行：两个整数n和k（1 ≤ 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的要求。

代码实现

#include<bits/stdc++.h>usingnamespacestd;intn,k,a[1000010];intcnt[1001];//计数数组，值≤1000intmain(){cin>>n>>k;for(inti=1;i<=n;i++)cin>>a[i];intdiff=0;//当前窗口不同整数的个数for(inti=1;i<=k;i++){//初始化第一个窗口if(cnt[a[i]]==0)diff++;//新值出现，种类数+1cnt[a[i]]++;}cout<<diff<<" ";//输出第一个窗口答案for(inti=k+1;i<=n;i++){//滑动窗口，i为右端点intout=a[i-k];//即将离开窗口的左端元素cnt[out]--;if(cnt[out]==0)diff--;//该值不再出现，种类数-1intin=a[i];//即将进入窗口的右端元素if(cnt[in]==0)diff++;//新值出现，种类数+1cnt[in]++;cout<<diff<<" ";//输出当前窗口答案}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++标准模板库STL：
https://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 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}