程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LeetCode:Longest Consecutive Sequence

LeetCode:Longest Consecutive Sequence

編輯:C++入門知識

LeetCode: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.

// https://oj.leetcode.com/problems/longest-consecutive-sequence/
// Author : Chao Zeng
// Date   : 2015-3-30
class Solution {
public:
    int longestConsecutive(vector &num) {
        map mp;
        const int NUM = 100;//由於數據中存在負數,所以數組元素加一個偏移量,保證數組下標有效性
        int length = num.size();
        for (int i = 0; i < length; i++){
            mp[num[i] + NUM] = 1;
        }

        int ans;
        int res = 0;
        for (int i = 0; i < length; i++){
            ans = 1;
            if (mp.count(num[i] + NUM)){
                int left = num[i] + NUM - 1;
                while (mp.count(left) && mp[left] != 0){
                    mp[left--] = 0;
                    ans++;
                }

                int right = num[i] + NUM + 1;
                while (mp.count(right) && mp[right] != 0){
                    mp[right++] = 0;
                    ans++;
                }
            }

            if (res < ans){
                res = ans;
            }
        }
        return res;
    }
};

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved