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<Integer> list = new ArrayList<Integer>(); 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); } }