為什么80%的碼農(nóng)都做不了架構(gòu)師？>>> ??

題目

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.

思路

• （預(yù)處理）保存一個哈希表（或者集合），用于o(1)時間查找該數(shù)字是否存在于數(shù)組當(dāng)中

• 數(shù)字有可能重復(fù)，所以其實哈希集合就夠了，典型的空間換時間

• （預(yù)處理）一個表征是否使用的used表，用于o(1)時間查找該數(shù)字是否已經(jīng)被包含在另外一個序列當(dāng)中

• 注意數(shù)字有可能是負數(shù)，所以直接用數(shù)組不好

• 輪詢數(shù)組，遇到一個數(shù)字，查找其左，右的最長連續(xù)序列長度，并記錄與已知最大長度相比較

代碼

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 usedfor (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;}} }

轉(zhuǎn)載于:https://my.oschina.net/zuoyc/blog/338719

總結(jié)

以上是生活随笔為你收集整理的[LeetCode] Longest Consecutive Sequence 求解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。