首页 > 试题广场 >

数字序列

[编程题]数字序列
  • 热度指数：1785 时间限制：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

输入

10
1
1
3
4
6
6
5
1
3
3

输出

6 3
[2,7] [3,8] [4,9]
算法知识视频讲解
添加回答
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;

struct P{
    int l, r;
};

int main(){
    set<int> S;
    unordered_map<int, int> mp;
    vector<P> r;
    int n, cnt=0, Min=INT_MAX;
    scanf("%d", &n);
    int a[n];
    for(int i=0;i<n;i++){
        scanf("%d", &a[i]);
        S.insert(a[i]);
    }
    int i=0;
    for(int j=0;j<n;j++){
        if(mp[a[j]] == 0)
            cnt++;
        mp[a[j]]++;
        while(cnt >= S.size()){
            if(mp[a[i]] == 1)
                cnt--;
            mp[a[i]]--;
            if(j-i+1 < Min){
                r.clear();
                Min = j-i+1;
                r.push_back({i, j});
            }else if(j-i+1 == Min)
                r.push_back({i, j});
            i++;       
        }
    }
    printf("%d %d\n", Min, (int)r.size());
    for(int i=0;i<r.size();i++)
        printf("[%d,%d] ", r[i].l+1, r[i].r+1);
    return 0;
}

发表于 2020-11-15 00:51:16 回复(0)
我回去等通知了头像 我回去等通知了 
#include<bits/stdc++.h>
using namespace std;

int main(){
#ifdef ONLINE_JUDGE
#else
     freopen("E:/input.txt", "r", stdin);
#endif
    unordered_map<int,int> mp;
    unordered_map<int,int> _mp;
    int n;
    scanf("%d",&n);
    vector<int>num;
    num.push_back(0);
    for(int i = 0; i < n; ++i)
    {
        int tmp;
        scanf("%d",&tmp);
        num.push_back(tmp);
        _mp[tmp] = 1;

    }

    int m = _mp.size();
    int cnt = 0;
    int ans = n+1;
    vector<pair<int,int> > res;
    for(int i = 1,j = 1; j <= num.size(); ++j)
    {
        if(!mp[num[j]])
            ++cnt;

        mp[num[j]]++;

        if(cnt == m)
        {
            while(mp[num[i]] > 1)
            {
                mp[num[i]]--;
                i++;
            }
            if(j - i + 1 < ans)
            {

                ans = j - i + 1;
                res.clear();
                res.push_back(pair<int,int>(i,j));
            }else if(j - i + 1 == ans)
            {
               res.push_back(pair<int,int>(i,j));
            }
        }

    }
    printf("%d %d\n",ans,res.size());
    for(int i = 0; i < res.size(); ++i)
    {
        printf("[%d,%d]",res[i].first,res[i].second);
        if(i < res.size()-1)
            printf(" ");
        else
        {
            printf("\n");
        }
    }


    return 0;
}
感谢评论区，用map会超时，用unordered_map就过了
编辑于 2020-03-09 22:46:28 回复(0)
饮冰室客人头像 饮冰室客人 
#include <bits/stdc++.h>
#define MAX_N 5000005
using namespace std;

int first[10000], second[10000];
int data[MAX_N];

int main(){
    int n; scanf("%d", &n);
    set<int> key;
    for(int i = 0; i < n; i++){
        scanf("%d", &data[i]);
        key.insert(data[i]);
    }
    int num = key.size();
    //求解
    int i = 0, j = 0;
    int count = 0;
    unordered_map<int, int> appear;
    
    while(i <= j && j <= n){
        //找齐了数字
        if(appear.size() == num){
            //第一次出现全部数字，或者出现的数字的区间等于最小的区间
            if(count == 0 ||second[count - 1] - first[count - 1] == j - i - 1){
                //区间编号从1到N
                first[count] = i + 1;
                second[count++] = j;
            }
            //有更小的区间出现，重新赋值区间
            else if(second[count - 1] - first[count - 1] > j - i -1){
                count = 0;
                first[count] = i + 1;
                second[count++] = j;
            }
            //进行下一步的搜索，i向前移动，并在已经出现的map中减去
            if(appear[data[i]] == 1)
                appear.erase(data[i]);
            else
                appear[data[i]] --;
            i ++;
        }
        //没有找齐，继续插入数字
        else
            appear[data[j++]] ++;
    }
    
    printf("%d %d\n", second[0] - first[0] + 1,  count);
    for(int i = 0; i < count; i ++)
        printf("[%d,%d]%c", first[i], second[i], i == count-1 ? '\n': ' ');
    
    return 0;
}

发表于 2019-08-21 11:50:55 回复(0)
容易201810201736325头像 容易201810201736325
用c++ cin和cout会卡时间，改用scanf和printf就好了
发表于 2019-03-23 21:15:24 回复(0)
泰山弟子头像 泰山弟子 
#include <iostream>
#include <set>
#include <vector>
#include <unordered_map>
using namespace std;

int main(){
    int n;
    scanf("%d", &n);
    vector<int> array(n,0);
    set<int> s;
    for(int i=0;i<n;i++){
        scanf("%d", &array[i]);
        s.insert(array[i]);
    }
    int left = 0, right = 0;
	vector<vector<int>> res;
	unordered_map<int, int> tmp;
	int min_len = n;
	while (right < n) {
		if (tmp.find(array[right]) == tmp.end())
			tmp[array[right]] = 1;
		else {
			tmp[array[right]]++;
		}
		if (tmp.size() == s.size()) {
			break;
		}
		right++;
	}
	while (right < n) {
		while ( right - left +1 >= s.size()  && tmp.size() == s.size()) {
			if (right - left + 1 <= min_len) {
				vector<int> t(2, 0);
				t[0] = left;
				t[1] = right;
				res.push_back(t);
				min_len = right - left + 1;
			}
			tmp[array[left]] --;
			if (tmp[array[left]] == 0) {
				tmp.erase(array[left]);
			}
			left++;
		}
		right++;
		if (tmp.find(array[right]) == tmp.end()) {
			tmp[array[right]] = 1;
		}
		else
			tmp[array[right]] ++;
	}
	int count = 0;
	for (int i = 0; i < res.size(); i++) {
		//cout << res[i][0] +1  << "--" << res[i][1] + 1<< endl;
		if (res[i][1] - res[i][0] + 1 == min_len) {
			count++;
		}
	}
    printf("%d %d\n", min_len, count);
	for (int i = 0; i < res.size(); i++) {
		if (res[i][1] - res[i][0] + 1 == min_len) {
            printf("[%d,%d] ", res[i][0] + 1, res[i][1] + 1 );
		}
	}
	printf("\n");
	return 0;
}

发表于 2019-08-17 16:28:31 回复(0)
Java
suwhvdhd头像 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)
牛客497864927号头像 牛客497864927号
滑动窗口+双指针；技巧：遍历右指针，对于每个右指针位置，while移动左指针，可以减少一些条件判断。 
#include <cstdio>
#include <iostream>
#include <vector>
#include <climits>
#include <unordered_set>
#include <unordered_map>
using namespace std;

int main()
{
    int n;
    scanf ("%d", &n);
    vector<int> A(n);
    unordered_set<int> Set;
    unordered_map<int, int> winHash;
    for (int i = 0; i < n; ++i)
    {
        scanf("%d", &A[i]);
        Set.insert(A[i]);
    }    

    vector<pair<int, int>> ans;
    int count = Set.size(), winnum = 0;
    int left = 0, right;
    int minlen = INT_MAX;
    for (right = 0; right < n; ++right)
    {
        if (winHash[A[right]]++ == 0) winnum++;
        while (left <= right && winnum == count)
        {
            if (right-left+1 < minlen)
            {
                minlen = right-left+1;
                ans.clear();
            }
            if (right-left+1 == minlen)
                ans.push_back({left+1, right+1});
            if (--winHash[A[left]] == 0)
                winnum--;
            left++;
        }
    }
    int nans = ans.size();
    printf("%d %d\n", minlen, nans);
    for (int i = 0; i < nans; ++i)
    {
        printf(" [%d,%d]"+!i, ans[i].first, ans[i].second);
    }
    printf("\n");

    return 0;
}

编辑于 2020-12-28 15:13:13 回复(0)
原反补移码头像 原反补移码 
滑动窗口思想  开始用cin超时  用scanf就没有这回事了。搞不懂搞不懂。
#include<iostream>
(720)#include<set>
#include<vector>
(721)#include<unordered_map>
#include<stdio.h>
using namespace std;

int main(void){
    int N;
    cin>>N;
    set<int> s;
    int num;
    int MinLen = 5000000;
    unordered_map<int, int> windows;
    vector<int> v;
    vector<vector<int>> ans;
    int n = 0;
    for (int i = 0; i < N; i++){
        scanf("%d", &num);
        s.insert(num);
        v.push_back(num);
    }
    int i = 0;
    for (int j = 0; j < N; j++){
        if (windows[v[j]] == 0)
            n++;
        windows[v[j]]++;
        while (n >= s.size()){
            if (windows[v[i]] == 1){
                n--;
            }
            windows[v[i]]--;
            if (j - i + 1 < MinLen){
                ans.clear();
                MinLen = j - i + 1;
                ans.push_back(vector<int> {i, j});
            }
            else if(j - i + 1 == MinLen){
                ans.push_back(vector<int> {i, j});
            }
            i++;
        }
        
    }
    cout<<MinLen<<" "<<ans.size()<<endl;
    for (int i = 0; i < ans.size(); i++){
        cout<<"["<<ans[i][0]+1<<","<<ans[i][1]+1<<"]"<<" ";
    }
    cout<<endl;
    return 0;
}

发表于 2020-05-10 10:25:13 回复(0)
++offer&&offer++头像 ++offer&&offer++
双指针+unordered_map
发表于 2019-09-13 11:49:03 回复(0)
Polestar_a头像 Polestar_a 
N = int(input())
from collections import defaultdict
d = set()
res = []
for i in range(N):
    temp = int(input())
    res.append(temp)
    if temp not in d:
        d.add(temp)
total = []
min_length = len(res)
temp = defaultdict(int)
start,end = 0,1
temp[res[0]] = 1
temp_len = 1
while(end<N+1):
    if temp_len==len(d):
        if end-start<min_length:
            total=[[start+1, end]]
            min_length = end-start
        elif end-start==min_length:
            total.append([start+1, end])
        if temp[res[start]]==1:
            temp_len-=1
        temp[res[start]]-=1
        start+=1
    else:
        if end <N and temp[res[end]]==0:
            temp_len+=1
        if end<N:
            temp[res[end]]+=1
        end+=1
    
print(min_length,len(total))
for i in total:
    print('['+str(i[0])+','+str(i[1])+']', end=' ')
print(end='\n')

发表于 2019-08-08 13:33:35 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 贪心 小米集团 搜狗 2019 Java工程师
来自：搜狗2019秋招研究员...
上传者：小小
难度：
10条回答 7249浏览

热门推荐

通过挑战的用户

查看代码

相关试题

数字序列

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号