找出最长连续子序列

桃扇骨 2022-05-21 05:17 219阅读 0赞

![这里写图片描述][70]

import java.util.*;
    public class Solution {
    
        //方法一:时间复杂度为O(nlog(n))
        public int longestConsecutive(int[] num) {
            if(num==null||num.length==0)
              return 0;
            Arrays.sort(num);
            ArrayList<Integer>list=new ArrayList<>();
            int count=1;
            for(int i=1;i!=num.length;i++){
              if(num[i]-num[i-1]==1){
                    count++;
              }else if(num[i]-num[i-1]==0)
              {
                   continue;
              }else{
                  list.add(count);
                  count=1;
              }  
            }
    
            for(int k:list){
                count=Math.max(count,k);
            }
            return count;
        }
    
        //方法二:时间复杂度为O(n)
        public int longestConsecutive2(int[] num){
    
             if(num==null||num.length==0){
                 return 0;
             }
             HashSet<Integer>set=new HashSet<>();
             for(int k:num){
                set.add(k);
             }
             int max=1;
             for(int k:num){
                  if(set.remove(k)){
                      int val=k;
                      int count=1;
                      int val_small=val-1;
                      int val_big=val+1;
                      while(set.remove(val_small)) {
                          count++;
                          val_small--;
                      }
                      while(set.remove(val_big)){
                          count++;
                          val_big++;
                      }
                      max=Math.max(max,count);
                  }
    
             }
             return max;
        }
    
        public static void main(String[]args){
            //System.out.println("Hello");
            Solution s=new Solution();
            int[]num={
       1,2,0,1};
            System.out.println(s.longestConsecutive(num));
            System.out.println(s.longestConsecutive2(num));
        }
    }

[70]: /images/20220521/d2cfc9bdd603425e9ab3308569f6f051.png