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

Longest Consecutive Sequence 數組連續數字的情況

編輯:C++入門知識

Longest Consecutive Sequence 數組連續數字的情況


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.

尋找最大的連續數組的長度,利用兩個set數組,一個數組存儲已經被訪問過的數組,如果已經被訪問過了,那麼就不需要再被訪問了

 

class Solution {
public:
    int longestConsecutive(vector& nums) {
        if(nums.empty())
        {
            return 0;
        }
        unordered_set existSet;
        unordered_set visitedSet;
        int maxLength = 0;
        for(int i = 0; i < nums.size(); i++)
            existSet.insert(nums[i]);
        for(int i = 0; i < nums.size(); i++)
        {
            int length = 0;
            if(visitedSet.count(nums[i]))
            {
                continue;
            }
            else
            {
                visitedSet.insert(nums[i]);
                length++;
                int left = nums[i];
                int right = nums[i];
                while(existSet.count(--left))
                {
                    visitedSet.insert(left);
                    length++;
                }
                while(existSet.count(++right))//<必須使用?前++
                {
                    visitedSet.insert(right);
                    length++;
                }
                maxLength = max(maxLength,length);
            }
        }
        return maxLength;
    }
};

 

First Missing Positive

 

 

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

連續數組求最小的miss的數據,還是利用前面介紹的方法,還是利用兩個不同的set,其中一個表示已經訪問過了的情況,只觀察比當前大的數據,

如果已經訪問過了就不訪問了

class Solution {
public:
    int firstMissingPositive(vector& nums) {
        if(nums.empty())
        {
            return 1;
        }
        int missVal = INT_MAX;
        int minVal = 1;
        unordered_set numSet;
        unordered_set visitedSet;
        for_each(nums.begin(),nums.end(),[&numSet](int x)
        {
            if(x >= 0)
                numSet.insert(x);
        });
        for(int i = 0; i < nums.size(); i++)
        {
            if(nums[i] < 0 || visitedSet.count(nums[i]))
            {
                continue;
            }
            int right = nums[i];
            while(numSet.count(++right))
            {
                visitedSet.insert(right);
            }
            missVal = min(missVal,right);
        }
        if(numSet.count(1))
            return missVal;
        else
        {
            return 1;
        }
    }
};

 



 

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