【题目】
Longest Consecutive Sequence
Total Accepted:4743Total
Submissions:17989My Submissions
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.
【题意】
给出一个没有排序的整数数组,找出最长的连续元素序列的长度。
例如,
给定[100,4,200,1,3,2],
最长的连续元素序列是[1,2,3,4]。返回它的长度:4。
你的算法应该运行在O(n)的复杂度。
【分析】
如果允许 O(n log n) 的复杂度,那么可以先排序,可是本题要求 O(n)。由于序列里的元素是无序的,又要求 O(n),首先要想到用哈希表。
用一个哈希表visited[]记录每个元素是否使用,对每个元素,以该元素为中心,往左右扩张,直到不连续为止,记录下最长的长度。
在[100,4,200,1,3,2,101,99,97,98,102]的例子中:
(1)第一步:以100为中心
向右扩张:101,102
向左扩张:99,98,97
(2)第二步:以4为中心
向右扩张:无
向左扩张:3,2,1
(3)第三步:以200为中心
向右扩张:无
向左扩张:无
(4)1,3,2,101........以被扩张,无需以他们为中心进行扩张
【代码】
/*********************************
* 日期:2014-01-17
* 作者:SJF0115
* 题号: Longest Consecutive Sequence
* 来源:http://oj.leetcode.com/problems/longest-consecutive-sequence/
* 结果:AC
* 来源:LeetCode
* 总结:
**********************************/
#include <iostream>
#include <stdio.h>
#include <vector>
#include <tr1/unordered_map>
using namespace std;
using namespace tr1;
class Solution {
public:
int longestConsecutive(vector<int> &num) {
int i,j;
int CurLength = 0;
int MaxLength = 0;
int Len = num.size();
// Map中的元素是自动按key升序排序
unordered_map<int,bool> used;
//初始化
for(i = 0;i < Len;i++){
used[num[i]] = false;
}
for(i = 0;i < Len;i++){
//如果以扩张,跳过
if(used[num[i]]){
continue;
}
else{
//以num[i]为中心左右扩张,直到不连续为止
used[num[i]] = true;
CurLength = 1;
//向右扩张
for(j = num[i] + 1;used.find(j) != used.end();j++){
CurLength ++;
used[j] = true;
}
//向左扩张
for(j = num[i] - 1;used.find(j) != used.end();j--){
CurLength ++;
used[j] = true;
}
//更新最大长度
if(CurLength > MaxLength){
MaxLength = CurLength;
}
}//if
}//for
return MaxLength;
}
};
int main() {
int result;
Solution solution;
vector<int> vec;
vec.push_back(100);
vec.push_back(4);
vec.push_back(200);
vec.push_back(1);
vec.push_back(3);
vec.push_back(2);
vec.push_back(101);
vec.push_back(99);
vec.push_back(97);
vec.push_back(98);
vec.push_back(102);
result = solution.longestConsecutive(vec);
printf("Result:%d\n",result);
return 0;
}
分享到:
相关推荐
用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现...
JVM 基础 JAVA 并发 JVM 性能调优 LeetCode 算法 .......
My Solutions to Leetcode Database problems. 我的 Leetcode 数据.zip
Leetcode 题解.pdf
LeetCode 后端.zip
Recording personal Java, Python, JavaScript solutions for Leetcode problems. 记录个人 Java, Python, JavaScript 的Leetcode题解.zip
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
Leetcode101.zip
刷leetcode总结.md
原创:leetcode 111. 二叉树的最小深度记住:最小深度和最大深度方法不同。* Definition for a binary tree node.in
原创:leetcode 107. 二叉树的层次遍历 II【队列】* Definition for a binary tree node.
原创:leetcode 5. 最长回文子串//寻找以i-1,i为中点偶数长度的回文//寻找以i为中心的奇数长度的回文。
原创:leetcode 22.括号生成【回溯】对待这种问题,千万别暴力搜索,那样太笨了。但是这个方法是最容易理解的//回溯法 (后面的括号) 不可以大于 (前面
My Solutions to Leetcode problems. All solutions support C
LeetCode674. 最长连续递增序列674. 最长连续递增序列解题思路:记录每次递增序列的长度,max存储最大长度// 递增序列更新最大长度} else
LeetCode746.使用最小花费爬楼梯746. 使用最小花费爬楼梯解题思路:动态规划当前楼梯最小值=Math.min(前一步最小值,前两步最小值)简化 mi
LeetCode888. 公平的糖果棒交换888. 公平的糖果棒交换解题思路:哈希表法第一次遍历 A\B 计算二者的糖果差值 diff,同时以 B糖果值建立哈希
84. 柱状图中最大的矩形 - 力扣(LeetCode).html