首页 > 试题广场 >

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

[编程题]找出数组中连续数据的长度
  • 热度指数: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)
/******
题目描述
输入一组未排序的整数,找出其中最长的连续数字的长度。
例如输入为[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)
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)