题解 | #数组中的最长连续子序列#
数组中的最长连续子序列
http://www.nowcoder.com/practice/eac1c953170243338f941959146ac4bf
思路:
1.先排序,这里我自己写了个快排,练一练手。
2.遍历数组
1)若前后连续,则计数值加1,再根max值比较,将大值赋给max。
2)不连续,则计数值变为1,仪当前数组值作为起点,重新开始寻找。
3.返回max
public int MLS (int[] arr) { // write code here int cnt=1; int max=1; Qsort(arr,0,arr.length-1); for(int i=1;i<arr.length;i++){ if(arr[i]-arr[i-1]==1){ cnt++; max=cnt>max?cnt:max; }else if(arr[i]!=arr[i-1]){ cnt=1; } } return max; } //快排 public void Qsort(int[] arr,int l,int h){ int pivot=0; if(l<h){ pivot=partition(arr,l,h); Qsort(arr,l,pivot-1); Qsort(arr,pivot+1,h); } } //得到中间值的索引 public int partition(int[] arr,int l,int h){ int mid=arr[l]; while(l<h){ while(l<h && arr[h]>=mid){ h--; } swap(arr,l,h); while(l<h && arr[l]<=mid){ l++; } swap(arr,l,h); } return l; } //交换l1和l2的数据 public void swap(int[] arr,int l1,int l2){ int tmp=arr[l1]; arr[l1]=arr[l2]; arr[l2]=tmp; }