首页 > 代码库 > 【LeetCode OJ】Longest Consecutive Sequence
【LeetCode OJ】Longest Consecutive Sequence
Problem Link:
http://oj.leetcode.com/problems/longest-consecutive-sequence/
This problem is a classical problem where we can reduce the running time by the help of hash table.
By given a list of numbers, we can find the longest consecutive sequence by the following steps:
- Let H be a empty hash set, add all given numbers into H (duplicates will be removed)
- Let max_len = 0 denote the length of current longest consecutive sequence
- While H is not empty:
- count all n‘s smaller consecutive numbers in H and remove them from H
- count all n‘s larger consecutive numbers in H and remove them from H
- update max_len with the length of this consecutive sequence containing n
The python code is as follows.
?
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 | class Solution: # @param num, a list of integer # @return an integer def longestConsecutive( self , num): """ Find the longest consecutive number sequence by using hash map 1) Add all numbers in the list to a hash set HS 2) Let max_length = 0, which records the length of the current longest consecutive sequence 3) For each number n in the hash set count the number of all n‘s left consecutive numbers in the hash set count the number of all n‘s right consecutive numbers in the hash set remove the counted numbers from the hash set Update the max_length with the length of this consecutive sequence contaning n. """ # Conver the list to a hash set, this will remove the duplicates numbers = set (num) # Current max_len max_len = 0 while numbers: # Get a number from the hash set x = numbers.pop() # This sequence only containing x is length of 1 x_len = 1 # Find all left consecutive numbers of x left = x - 1 while left in numbers: numbers.remove(left) left - = 1 # Find all right consecutive numbers of x right = x + 1 while right in numbers: numbers.remove(right) right + = 1 # Update the max_len max_len = max (max_len, right - left - 1 ) return max_len |
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。