LeetCode 题解（93）: Longest Consecutive Sequence

本文主要是介绍LeetCode 题解（93）: 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(n)时间，所以不能排序。用set或map保存nums的值，然后取set或map中的一个元素，从set或map中删除当前元素并查看该元素+1,该元素-1是否在set或map中，如果在就增加currentLongest，并相应的删除该元素+1,该元素-1。以此类推。

c++版：

class Solution {
public:int longestConsecutive(vector<int>& nums) {unordered_set<int> exist;for(auto i : nums)exist.insert(i);int longest = 0;while(exist.size() != 0) {int current = *exist.begin();exist.erase(exist.begin());int currentLongest = 1;int j = 1;if(current + j < INT_MAX && exist.find(current + j) != exist.end()) {while(exist.find(current + j) != exist.end()) {currentLongest++;exist.erase(current+j);j++;}}j = 1;if(current - j > INT_MIN && exist.find(current - j) != exist.end()) {while(exist.find(current - j) != exist.end()) {currentLongest++;exist.erase(current - j);j++;}}if(currentLongest > longest)longest = currentLongest;}return longest;}
};

Java版：

public class Solution {public int longestConsecutive(int[] nums) {Set<Integer> exist = new HashSet<>();for(int i : nums)exist.add(i);int longest = 0;while(exist.isEmpty() == false) {Iterator<Integer> iter = exist.iterator();if(iter.hasNext()) {int current = iter.next();exist.remove(current);int currentLongest = 1;int j = 1;if(current + j <= Integer.MAX_VALUE && exist.contains(current+j)) {while(exist.contains(current+j)) {currentLongest++;exist.remove(current+j);j++;}}j = 1;if(current - j >= Integer.MIN_VALUE && exist.contains(current-j)) {while(exist.contains(current-j)) {currentLongest++;exist.remove(current-j);j++;}}if(currentLongest > longest) {longest = currentLongest;}}}return longest;}
}

Python版：

class Solution:# @param {integer[]} nums# @return {integer}def longestConsecutive(self, nums):exist = set()for i in nums:exist.add(i)longest = 1while len(exist) != 0:current = exist.pop()currentLongest = 1j = 1while current + j in exist:currentLongest += 1exist.remove(current + j)j += 1j = 1while current - j in exist:currentLongest += 1exist.remove(current - j)j += 1if currentLongest > longest:longest = currentLongestreturn longest

这篇关于LeetCode 题解（93）: Longest Consecutive Sequence的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---