leetcode — longest-consecutive-sequence

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

import java.util.HashSet;
import java.util.Set;/**
* Source : https://oj.leetcode.com/problems/longest-consecutive-sequence/
*
*
* Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
*
* For example,
* Given [100, 4, 200, 1, 3, 2],
* The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
*
* Your algorithm should run in O(n) complexity.
*/
public class LongestConsecutiveSequence { /**
* 求出数组中元素能构成连续序列的最大长度
*
* 题目中要求是O(n)，所以不能使用排序的办法
* 针对每个元素arr[i]寻找数组中向前、向后有没有能构成连续序列的元素，查找的时候利用hash表
* 每次记录最大长度，如果找到了就把该元素从hash表中删除，因为该元素不会被再次查找到，所以从hash表中移除
* 如果hash表为空了，说明所有元素都被查找过，退出循环
*
* @param arr
* @return
*/
public int findLongestSequence (int[] arr) {
int max = 0;
Set<Integer> set = new HashSet<Integer>(arr.length);
for (int i = 0; i < arr.length; i++) {
set.add(arr[i]);
} for (int i = 0; i < arr.length; i++) {
int curnum = arr[i] - 1;
int len = 1; // 查找curnum左边的数字
while (set.contains(curnum)) {
set.remove(curnum);
curnum -= 1;
len++;
} curnum = arr[i] + 1;
while (set.contains(curnum)) {
set.remove(curnum);
curnum += 1;
len++;
} max = Math.max(max, len);
if (set.size() <= 0) {
return max;
}
}
return max;
} public static void main(String[] args) {
LongestConsecutiveSequence longestConsecutiveSequence = new LongestConsecutiveSequence();
System.out.println(longestConsecutiveSequence.findLongestSequence(new int[]{100, 4, 200, 1, 3, 2}) + "----4");
}
}