[LeetCode]128.Longest Consecutive Sequence-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

[LeetCode]128.Longest Consecutive Sequence

简介:

【题目】

Longest Consecutive Sequence

 Total Accepted: 4743 Total 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;
}






版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章
最新文章
相关文章