Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given
The longest consecutive elements sequence is
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.
Another problem can be solved by hash map! I remember one of my SWE friend posted on FB about hash map: "It's incredibly fast!"Well, I haven't reached to that state. But using hash map does have lots of convenience.
This problem, we use a HashMap <Integer, Integer> to track if the number in the array has been counted in one of the sequences. The key is the element, the value is either 0 (not in any sequence) and 1 (already in a sequence).
We search the map to get the sequence for a particular element, and compare to the longest sequence so far.
public class LongestSequence { public int longestConsecutive(int[] num) { if (num == null || num.length == 0) return 0; HashMaphm = new HashMap (); for (int i : num) hm.put(i, 0); int max = 1; for (int i : num) { //already checked as part of a sequence if (hm.get(i) == 1) continue; int tmp = i; int currmax = 1; while(hm.containsKey(tmp+1)) { currmax++; hm.put(tmp, 1); tmp++; } tmp = i; while (hm.containsKey(tmp-1)) { currmax++; hm.put(tmp,1); tmp--; } max = Math.max(max, currmax); } return max; } }
No comments:
Post a Comment