网站设计师专业,网站改版要多少钱,如何做网站首页的psd图,天津建筑工程信息网一、问题描述
给定 n 个数形成的一个序列 a#xff0c;现定义如果一个连续子序列包含序列 a 中所有不同元素#xff0c;则该连续子序列便为蓝桥序列#xff0c;现在问你#xff0c;该蓝桥序列长度最短为多少#xff1f;
例如 1 2 2 2 3 2 2 1#xff0c;包含 3 个不同的…一、问题描述
给定 n 个数形成的一个序列 a现定义如果一个连续子序列包含序列 a 中所有不同元素则该连续子序列便为蓝桥序列现在问你该蓝桥序列长度最短为多少
例如 1 2 2 2 3 2 2 1包含 3 个不同的数 1,2,3而 3 2 2 1 符合题目要求因此答案为 4。
连续子序列从序列 a 中选取若干个连续的数形成一个序列叫连续子序列。
输入格式
第一行输入一个整数 n表示序列长度。
第二行输入 n 个元素。
输出格式
输出一个整数表示最短的蓝桥序列长度。
样例输入
8
1 2 2 2 3 2 2 1样例输出
4 二、代码展示
import java.util.*;public class 全部都有的子序列_二分_滑动窗口 {public static void main(String[] args) {Scanner scnew Scanner(System.in);int n sc.nextInt();int []arrnew int[n];SetInteger setnew HashSet();for (int i 0; i n; i) {arr[i] sc.nextInt();set.add(arr[i]);}int l0,rn;int mset.size();//set存储不重复的数字while(lr){int mid(lr)/2;if(check(mid,arr,m)) rmid;else lmid1;}System.out.println(l);}public static boolean check(int mid,int []arr,int m){//滑动窗口求解int narr.length;int []fnew int[1001];//记录出现频率int l0,r0;//双指针int ans0;//统计当前窗口的不同元素数量while(rn) {//右指针没有到达数组最右边f[arr[r]];//记录一个数的频率if(f[arr[r]]1){ ans;}if(r-l1mid) {//当区间距离mid,说明此时并没有满足ansmf[arr[l]]--;//左指针对应减一if(f[arr[l]]0){//说明之前只有一个,减去后变成零,这个时候一个数字消失,对应的ans应减一ans--;}l;//左指针右移}r;//右指针一直右移if(ansm) return true;}return false;}
} 这段代码的目标是找到数组中最短的连续子序列该子序列包含数组中所有不同的元素。采用二分查找结合滑动窗口的方法高效地确定最小长度。 代码结构 主函数 读取输入数组并用集合统计不同元素的数量m。 使用二分查找确定最小窗口长度初始范围[0, n]。 每次计算中间值mid调用check函数验证是否存在长度为mid的窗口满足条件。 根据验证结果调整二分边界最终输出最小长度l。 check函数 使用滑动窗口和频率数组判断是否存在长度不超过mid的子序列包含所有m个不同元素。 维护窗口的左右指针l和r动态调整窗口大小。 统计窗口内不同元素的数量ans若达到m则返回true。 详细步骤解释 1. 主函数逻辑 输入处理读取数组并用HashSet统计不同元素的数量m。 二分查找初始化左边界l设为0最小可能长度右边界r设为数组长度n最大可能长度。 二分过程 计算中间值mid (l r) / 2。 调用check(mid, arr, m)判断是否存在长度为mid的窗口。 若存在说明答案可能更小调整右边界r mid否则调整左边界l mid 1。 终止条件当l r时l即为最小窗口长度。 2. check函数逻辑 初始化频率数组f记录元素出现次数双指针l和r初始为0ans统计当前窗口的不同元素数量。 滑动窗口过程 右指针扩展r右移增加元素频率。若元素首次出现ans加1。 窗口大小控制当窗口长度超过mid时左指针右移减少对应元素频率。若元素频率减至0ans减1。 条件检查每次调整后若ans m立即返回true存在满足条件的窗口。 遍历结束若未找到满足条件的窗口返回false。 关键点分析 二分查找的应用利用答案的单调性若长度为k可行则更大长度必然可行将时间复杂度优化至O(n log n)。 滑动窗口的灵活性不固定窗口大小而是允许在不超过mid的范围内动态调整一旦满足条件立即返回。 频率数组的作用快速统计窗口内不同元素的数量通过增减频率判断元素是否存在于当前窗口。 示例说明 假设数组为[1, 2, 3, 1, 2, 3, 4]不同元素数量m4。 二分初始范围[0,7]第一次mid3检查是否存在长度为3的窗口包含4个不同元素显然不可能。 调整边界最终找到最小长度为4如子序列[3, 1, 2, 4]或[1, 2, 3, 4]。 总结 该算法通过二分查找快速缩小搜索范围结合滑动窗口高效验证确保在合理时间复杂度内找到最优解。核心在于理解二分与滑动窗口的协同作用以及频率数组维护窗口状态的技巧。 详解check方法 1. 初始化参数 频率数组f记录当前窗口中各元素的出现次数索引对应元素值。 双指针l和r初始均为0分别表示窗口的左右边界。 计数器ans统计窗口内不同元素的数量初始为0。 2. 扩展右指针窗口右移 遍历数组右指针r从0开始逐步右移处理每个元素。 更新频率将arr[r]的频率f[arr[r]]加1。 f[arr[r]]; 唯一性判断若该元素首次出现在窗口频率由0变1则ans加1。 if (f[arr[r]] 1) ans; 3. 收缩左指针控制窗口大小 窗口长度检查当窗口长度r - l 1超过mid时需收缩左边界。 if (r - l 1 mid) { // 调整左指针 } 左移操作 减少左指针元素频率f[arr[l]]--。 唯一性减少若元素频率减至0说明该元素不再存在于窗口ans减1。 if (f[arr[l]] 0) ans--; 左指针右移l。 4. 实时检查条件满足 完成调整后每次右指针移动并调整窗口后立即检查ans是否达到m所有不同元素数量。 if (ans m) return true; 提前返回一旦满足条件立即返回true无需遍历整个数组。 5. 遍历结束处理 循环结束仍未满足若遍历完数组仍未找到符合条件的窗口返回false。 6.示例说明 以数组[1,2,3,1,2,3,4]和mid4为例 窗口逐步扩展至包含元素1,2,3此时ans3。 右指针到元素4时窗口包含1,2,3,4ans4但窗口长度5超过mid4。 收缩左指针至索引3窗口变为[1,2,3,4]长度4满足条件返回true。 边界情况处理 元素全相同若数组元素全为5m1窗口长度1即满足。 最小可能窗口当mid1且存在唯一元素时直接返回true。 总结 check方法通过滑动窗口在O(n)时间内验证是否存在满足条件的子数组结合二分查找高效定位最小长度确保整体时间复杂度为O(n log n)。
