Question: https://oj.leetcode.com/problems/longest-consecutive-sequence/
Question Name: Longest Consecutive Sequence
The requirement should be more accurate: your algorithm should run in O(n) complexity in average condition. I googled the other solutions. All of them used the hash table. But hash table’s time complexity is O(1) in average, and O(n) in worst case. So this solution have time complexity of O(n) in average, and O(n^2) in worst. In contrast, the sort-then-search solution can guarantee the worst complexity be O(nlogn).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | class Solution: # @param num, a list of integer # @return an integer def longestConsecutive(self, num): # Key (begin, exclusive) => Value (end, inclusive) segments = {} # Key (end, exclusive) => Value (begin, inclusive) reversedSegments = {} for item in set(num): if item in segments and item in reversedSegments: # This item could connect two segments. newEnd = segments[item] del segments[item] newBegin = reversedSegments[item] del reversedSegments[item] segments[newBegin-1] = newEnd reversedSegments[newEnd+1] = newBegin elif item in segments: # This item could extend one segment's beginning. oldEnd = segments[item] del segments[item] segments[item-1] = oldEnd reversedSegments[oldEnd+1] = item elif item in reversedSegments: # This item could extend one segment's end. oldBegin = reversedSegments[item] del reversedSegments[item] segments[oldBegin-1] = item reversedSegments[item+1] = oldBegin else: # No adjacent segment. This item will create a new segment. segments[item-1] = item reversedSegments[item+1] = item # Find the length of the longest segment. maxLen = 0 for segmentBegin in segments: segmentEnd = segments[segmentBegin] maxLen = max(maxLen, segmentEnd- segmentBegin) return maxLen |