首页 > 代码库 > [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.
思路
(预处理)保存一个哈希表(或者集合),用于o(1)时间查找该数字是否存在于数组当中
- 数字有可能重复,所以其实哈希集合就够了,典型的空间换时间
(预处理)一个表征是否使用的used表,用于o(1)时间查找该数字是否已经被包含在另外一个序列当中
- 注意数字有可能是负数,所以直接用数组不好
轮询数组,遇到一个数字,查找其左,右的最长连续序列长度,并记录与已知最大长度相比较
public class Solution { public int longestConsecutive(int[] num) { Map<Integer, Integer> map = new HashMap<Integer, Integer>(); for (int i = 0; i < num.length; i++) { map.put(num[i], i); } Map<Integer, Boolean> used = new HashMap<Integer, Boolean>(); for (int i : num) { used.put(i, false); } int max = Integer.MIN_VALUE; for (int i = 0; i < num.length; i++) { if (!used.get(num[i])) { used.put(num[i], true); int k = num[i]; int leftLength = findLength(k, map, "left"); int rightLength = findLength(k, map, "right"); // mark used for (int j = 0; j < leftLength; j++) { used.put(k - j - 1, true); } for (int j = 0; j < rightLength; j++) { used.put(k + j + 1, true); } int total = leftLength + rightLength + 1; if (total > max) { max = total; } } } return max; } private int findLength(int k, Map<Integer, Integer> map, String direction) { if ("left".equals(direction)) { int l = k - 1; while (map.containsKey(l)) { l -= 1; } return k - l - 1; } else { int l = k + 1; while (map.containsKey(l)) { l += 1; } return l - k - 1; } } }
[LeetCode] Longest Consecutive Sequence 求解
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。