撬动offer：基于一道算法题的分析
点击上方「蓝字」关注我们
0x01：算法题
给定无序数组arr，返回其中最长的连续序列的长度(要求值连续，位置可以不连续,例如 1,2,3,4为连续的自然数）
示例1
输入 {100,4,200,1,3,2}
输出 4
示例2 输入 {200,201,202,100,4,200,1,3,2,204,203}
输出 5
0x02：分析
从题目分析我认为主要有两个考点：
排序
连续数字最长子串
但是具体要看面试官的阐述，比如如果面试官说可以使用系统自带的排序，那么就不要纠结到底使用冒泡排序，还是快速排序；直接使用Collections的sort方法即可。
从力扣上看下，有不少跟子串相关的算法题
0x03：参考实现
如下这个答案应该也算是一个暴力破解了，看看大家有没有更优的解法
import java.util.Scanner;
import java.util.*;
import java.lang.Integer;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String lineStr = scanner.nextLine();
String[] elements = lineStr.split(" ");
List list = new ArrayList();
for (int i = 0; i < elements.length; i++) {
Integer val = Integer.parseInt(elements[i]);
if(!list.contains(val)){
list.add(val);
}
}
Collections.sort(list);
System.out.println(list);
int targetLen = 0;
int startNum = list.get(0);
int currentMaxLen = 1;
for (int k = 1; k < list.size(); k++) {
int e = list.get(k);
startNum = startNum + 1;
if ( e == startNum) {
currentMaxLen = currentMaxLen + 1;
} else {
if (currentMaxLen > targetLen) {
targetLen = currentMaxLen;
}
startNum = list.get(k);
currentMaxLen = 1;
System.out.println(startNum);
}
if(k == list.size()-1){
if (currentMaxLen > targetLen) {
targetLen = currentMaxLen;
}
}
}
System.out.println(targetLen);
}
} 
扫码二维码
获取更多精彩
Java乐园
评论