首页 > 代码库 > 【LeetCode】Longest Consecutive Sequence 解题报告
【LeetCode】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.
【题意】给定一个没有排序的数组,找出最长的连续子序列,返回其长度。
例如:给定[100, 4, 200, 1, 3, 2],其最长的连续子序列是[1, 2, 3, 4],所以返回其长度4。
算法复杂度需为O(n)。
【方法一】
用一个HashSet,首先把所有元素放进去;然后再逐个遍历每一个元素,查看该元素的左边相邻的数是否也在HashSet中,如果在,把其从HashSet中删除,继续向左找;右边也如此。
public class Solution { public int longestConsecutive(int[] num) { if (num == null || num.length < 1) return 0; Set<Integer> set = new HashSet<Integer>(); for (int x : num) { set.add(x); } int ans = 1; for (int x : num) { int left = x - 1; int right = x + 1; int count = 1; while (set.contains(left)) { set.remove(left); left--; count++; } while (set.contains(right)) { set.remove(right); right++; count++; } ans = Math.max(count, ans); } return ans; } }
来子:http://www.programcreek.com/2013/01/leetcode-longest-consecutive-sequence-java/
【方法二】
用一个HashMap来存储元素x所处的连续序列的长度,遍历num中的每一个元素x,查看x-1和x+1是否已经存在与某个连续的序列中,如果是,则x把这两个序列给连接起来了,x对应的序列长度就是这两个序列的长度的和再加1,同时要更新新的序列中每个元素对应的序列长度。如果HashMap中已经存在元素x,则说明x所处的序列已经被访问过,直接跳过。
public class Solution { public int longestConsecutive(int[] num) { int ans = 1; // Store num[i]'s consecutive sequence length. HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); for (int x : num) { if (!map.containsKey(x)) { int left = map.containsKey(x - 1) ? map.get(x - 1) : 0; int right = map.containsKey(x + 1) ? map.get(x + 1) : 0; int sum = left + right + 1; map.put(x, sum); ans = Math.max(ans, sum); map.put(x - left, sum); map.put(x + right, sum); } } return ans; } }
来自:https://oj.leetcode.com/submissions/detail/17876074/
【LeetCode】Longest Consecutive Sequence 解题报告