首页 > 试题广场 >

数字序列

[编程题]数字序列

热度指数：1662 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

一个由若干个取值范围在[1,2^31-1]的整数构成长度为N的数字序列，其中N<=5,000,000；求该数字序列上一段最小的连续区间的长度，要求该区间内正好包含了所有不同的数字，如果存在多个这样的区间，按照出现的顺序有序输出所有的区间起始和结束位置，序列的位置编号从1到N，其中最小的区间长度不会超过10,000。

输入描述:

第一行：N
第2至N+1行：每行1个数

输出描述:

第一行：最小的区间长度 区间个数X (以空格进行分隔）
第二行：X个区间的起始和结束位置，按照出现的顺序有序输出，多个区间之间以空格分隔，每个区间的输出格式如下所示：[start,end]，最后以换行结尾

示例1

输入

输出

6 3
[2,7] [3,8] [4,9]

算法知识视频讲解

Java

suwhvdhd

java代码，输入用next（）就行，用nextInt超时

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextInt()) { // 注意 while 处理多个 case
int n = in.nextInt();
int[] nums = new int[n];
Set<Integer> set = new HashSet<>();
for(int i = 0; i < n; i++){
nums[i] = Integer.parseInt(in.next());
set.add(nums[i]);
}
int count = set.size();
Map<Integer, Integer> map = new HashMap<>();
int start = 0;
int end = 0;
int res = 0;
int minL = Integer.MAX_VALUE;
List<Integer> list = new ArrayList<>();
StringBuilder sb = new StringBuilder();
while(end < n){
map.put(nums[end], map.getOrDefault(nums[end], 0) + 1);
while(start <= end && map.size() == count){
int num = map.get(nums[start]);
if(num == 1){
if(minL > end - start + 1){
minL = end - start + 1;
res = 0;
sb = new StringBuilder();
}
if(minL >= end - start + 1){
res++;
sb.append("[" + (start + 1) + "," + (end + 1) + "]" + " ");
}
map.remove(nums[start]);
}
else{
map.put(nums[start], num - 1);
}
start++;
}
end++;
}
System.out.println(minL + " " + res);
System.out.println(sb.toString());
}
}
}

发表于 2022-09-13 10:46:40 回复(0)