首页 > 试题广场 >

找出数组中连续数据的长度

[编程题]找出数组中连续数据的长度
  • 热度指数:780 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
输入一组未排序的整数,找出其中最长的连续数字的长度。例如输入为[3,1,2,5,7,4,8,9] ,其中连续的数据为1,2,3,4,5,长度为5 。要求算法时间复杂度为O(n).本题会人工判卷,请严格按照复杂度完成算法。

输入描述:
输入数据包括一行:
一共n个整数,范围均在32位整数内,格式见输入样例


输出描述:
输出最长的连续数字的长度
示例1

输入

[3,1,2,5,7,4,8,9]

输出

5
运行时间:10ms
超过100.00%用Java提交的代码
占用内存:9276KB
超过50.00%用Java提交的代码

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Set;
import java.util.HashSet;
public class Main{
    
    public static void main(String[] args) throws IOException{
        BufferedReader sc= new BufferedReader(new InputStreamReader(System.in));
        String input = sc.readLine();
        input = input.substring(1,input.length()-1);
        String[] inputData = input.split(",");
        int n = inputData.length;
        int[] matrix = new int[n];
        
        int[] fuzhu = new int [32];
        Set<Integer> set= new HashSet<>();
       
        for(int i = 0; i<n;i++){
            matrix[i] = Integer.parseInt(inputData[i]);
            set.add(matrix[i]);
        }
        
        for(int i =0; i<32;i++){
            fuzhu[i]=-1;
        }
        
        for(Integer num : set){
            fuzhu[num]=1;
        }
        
        int maxLen = 0;
        int len = 0;
        for(int i = 0 ;i<32;i++){
            if(fuzhu[i]>0){
                len++;
                maxLen = Math.max(maxLen,len);
            }
            else{
                len = 0;
                
            }
        }
        
        System.out.println(maxLen);
    }
}

发表于 2021-03-19 22:59:06 回复(0)
import java.util.HashSet;
import java.util.Scanner;

public class Main {

    public static int getMaxCount(String []nums){
        HashSet<Integer> data = new HashSet<>();
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for(int i=0;i<nums.length;i++){
            int input = Integer.valueOf(nums[i]);
            data.add(input);
            if(input<min){
                min = input;
            }
            if(input>max){
                max = input;
            }
        }
        int count = 1;
        int maxCount = 1;
        for(int i = min+1;i<=max;i++){
            if(data.contains(i)){
                count++;
                if(count>maxCount){
                    maxCount = count;
                }
            }else{
                count = 0;
            }
        }
        return maxCount;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String inputData = sc.nextLine();
        inputData = inputData.substring(1,inputData.length()-1);//去括号
        String nums[] = inputData.split(",");
        System.out.println(getMaxCount(nums));
    }
}
输入还特喵带括号。。。
编辑于 2017-09-03 00:23:36 回复(4)
import java.util.*;

public class Main {
    // 数组中最长连续的长度-o(n)
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        String[] ss = s.substring(1, s.length()-1).split(",");
        Set<Integer> set = new HashSet<>();
        for (String value : ss) {
            set.add(Integer.parseInt(value));
        }
        int cnt, max = 0;
        for (String value : ss) {
            cnt = 1;
            int n = Integer.parseInt(value);
            if (set.contains(n + 1)) {
                while (set.contains(n+1)) {
                    cnt++;
                    n++;
                }
            }
            max = Math.max(max, cnt);
        }
        System.out.println(max);
    }
}
发表于 2022-07-25 12:37:28 回复(0)
s = input().strip('[').strip(']').split(',')
s = list(map(int,s))
s = list(sorted(list(set(s))))
#print(s)

a = 1
lst = []
for i in range(len(s)-1):
    if s[i] + 1 == s[i+1]:
        a += 1
    else:
        a = 1
    lst.append(a)

print(max(lst))    
发表于 2022-06-07 20:04:08 回复(0)
#include<iostream>
#include<queue>
#include<vector>
#include<sstream>
#include<string>

using namespace std;

int main()
{
    //越小的优先级越高
    priority_queue<int,vector<int>,greater<int>> q;

    string str1;
    getline(cin,str1);
    
    stringstream ss(str1);
    char x;
    int num = 0;
    while(ss>>x)
    {
        if(x == ']')
            break;
        ss>>num;
        q.push(num);
    }
    //开始查找连续的数据,优先队列已经给里面的数据进行了排序
    int maxlen = 0;
    int len = 1;
    int size = q.size();
    for(int i= 0; i < size; i++)
    {
        int temp = q.top();
        q.pop();
        //说明是连续的
        if(q.top() - temp == 1)
            len++;
        else
        {
            len = 1;
        }

        maxlen = max(maxlen , len);
    }

    cout << maxlen << endl;

}
发表于 2021-07-08 14:58:45 回复(0)
num =input().replace('[', '').replace(']', '').split(',')
s =set()
for i in num:
    s.add(int(i))
s = list(s)    
res,ans = 1,0
for i in range(len(s)-1):
    if s[i+1]-s[i]==1:
        res+=1
        ans = max(ans, res)
    else:
        
        res = 1
if ans == 0:
    ans = 1
print(ans) 
发表于 2021-05-18 11:21:01 回复(0)
这题的测试数据也太水了吧,最大的数据也只有13个数。。。。。
发表于 2021-04-29 01:14:04 回复(0)
public class Main {
    public static void main(String[] args) {
        Scanner s=new Scanner(System.in);
        String nums=s.nextLine();
        String a[]=nums.substring(1,nums.length()-1).split(",");
        int b[]=new int[a.length];
        int max=0,count=0;
        for(int i=0;i<a.length;i++){
            b[i]=Integer.parseInt(a[i]);
            if(max<b[i])max=b[i];
        }
        int c[]=new int[max+1];
        for(int i=0;i<b.length;i++){
                c[b[i]]++;
        }
        int temp=0;
        for(int i=0;i<max+1;i++){
            if(c[i]!=0){
                temp+=c[i];
            }else  temp=0;
            count=Math.max(count,temp);
        }
        System.out.println(count);
    }
}


编辑于 2020-06-06 16:02:12 回复(0)
/******
题目描述
输入一组未排序的整数,找出其中最长的连续数字的长度。
例如输入为[3,1,2,5,7,4,8,9] ,其中连续的数据为
1,2,3,4,5,长度为5 。要求算法时间复杂度为O(n).
本题会人工判卷,请严格按照复杂度完成算法
*********/

import java.util.*;
import java.lang.*;

public class Main{
    static int maxLength(Set<Integer> set){
        int large = 0;
        boolean flag = true;
        int upnum = 0; //上边界
        int downnum = 0;//下边界
        for(Integer tmp:set){
            if(flag){//第一个数据更新为上、下边界,之后的就是在查找范围后更新
                flag = false;
                upnum = tmp;
                downnum = tmp;
            }
            if(tmp > upnum || tmp < downnum){
                int up = 0;//比当前数值大的且连续的数值有多少
                int down = 0;//比当前数值小的且连续的数值有多少
                int index = tmp + 1; //向上开始找
                while(set.contains(index)){
                    up++;
                    index++;
                }
                upnum = index;//更新上边界
                index = tmp - 1;//向下查找
                while(set.contains(index)){
                    down++;
                    index--;
                }
                downnum = index;//跟新下边界
                large = Math.max(up+down+1,large);//更新最大值
            }
        }
        return large;
    }
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        String input = in.nextLine();
        input = input.substring(1,input.length() - 1);
        String[] nums = input.split(",");
        Set<Integer> set = new HashSet<>();
        for(int i = 0;i < nums.length;i++){
            set.add(Integer.parseInt(nums[i]));
        }
        System.out.println(maxLength(set));
        in.close();
    }
}

发表于 2020-03-10 14:52:47 回复(0)
#include<bits/stdc++.h>
using namespace std;

int main(){
    string s;
    getline(cin,s);
    stringstream ss(s);
    vector<int> a;
    char x;
    int n;
    // 数据获取
    while(ss>>x){
        if(x == ']')
            break;
        ss>>n;
        a.push_back(n);
    }
    sort(a.begin(),a.end());
    int Max = 0,Count = 1;
    for(int i=1;i<a.size();i++){
        if(a[i-1]+1 == a[i])
            Count++;
        else{
            Max = max(Max,Count);
            Count = 1;
        }
    }
    Max = max(Max,Count);// 当循环跳出后还需进行比较
    cout << Max <<endl;
    return 0;
}

编辑于 2020-02-02 13:11:34 回复(0)
为什么带喵星括号??
发表于 2018-09-13 15:38:36 回复(0)
leetcode第128题

import java.util.*;
public class Main {
    public static int longestConsecutive(int[] nums){
        Set<Integer> set = new HashSet<>();
        for(int num:nums){
            set.add(num);
        }
        int longestStreak = 0;
        for(int num:set){
            if(!set.contains(num-1)){
                int currNum = num;
                int currStreak = 0;
                while(set.contains(currNum)){
                    currNum++;
                    currStreak++;
                }
                longestStreak = Math.max(longestStreak, currStreak);
            }
        }
        return longestStreak;
    }
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        String input = scan.nextLine();
        input = input.substring(1,input.length()-1);
        String[] inputArray = input.split(",");
        int[] inputNum = new int[inputArray.length];
        for(int i=0; i<inputNum.length; i++){
         inputNum[i] = Integer.parseInt(inputArray[i]);
        }
        System.out.println(longestConsecutive(inputNum));
   }
}
NowCoder的评判系统是真的不好用,还要自己写一个main函数来读取输入,鬼知道它输入的是个什么鬼东西。
编辑于 2018-03-19 23:41:10 回复(0)
答案解析里使用了HashMap.keyset()并没有进行排序。而输入又是乱序的,怎么保证排序后计算长度的?求解答。我觉得应该把HashMap换成TreeMap
发表于 2017-09-12 08:21:49 回复(0)
//输入一组未排序的整数,找出其中最长的连续数字的长度。例如输入为[3,1,2,5,7,4,8,9] ,
//其中连续的数据为1,2,3,4,5,长度为5 。要求算法时间复杂度为O(n).本题会人工判卷,请严格按照复杂度完成算法。
//

//关键是用到了桶排序

import java.util.Scanner;

public class Main {

public static void main(String[] arg){
Scanner scanner = new Scanner(System.in);
String inputStr = scanner.nextLine();
scanner.close();
System.out.println( count(inputStr) );
}
public static int count(String inputStr) {
if (inputStr == null || inputStr == "" || inputStr.length() < 2
|| !inputStr.startsWith("[") || !inputStr.endsWith("]")) {
return -1;
}

String dataInputStr = inputStr.substring(1, inputStr.length() - 1);
if (dataInputStr.length() == 0) {
return 0;
} else if (!dataInputStr.contains(",")) {
return 1;
} else {
String[] datas = dataInputStr.split(",");
int[] nums = new int[datas.length];
for (int i = 0; i < datas.length; i++) {
nums[i] = Integer.parseInt(datas[i]);
}
int maxValue = 0;
for (int i = 0; i < nums.length; i++) {
maxValue = nums[i] > maxValue ? nums[i] : maxValue;
}

boolean[] temp = new boolean[maxValue + 1];
for (int i = 0; i < nums.length; i++) {
temp[nums[i]] = true;
}

int result = 0;
int count = 0;
for (int i = 0; i < temp.length; i++) {
if (temp[i]) {
count++;
} else {
count = 0;
}
result = count > result ? count : result;
}

return result > 0 ? result : 1;
}

}

}

发表于 2017-08-31 23:13:13 回复(0)