本文主要是介绍找出最长连续子序列,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
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));}
}
这篇关于找出最长连续子序列的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!