【每日一題】leetcode刷題指南之Longest Consecutive Sequence

2021-02-20 機器學習算法與自然語言處理

給你一個未排序的數組，要在O(n)的時間複雜度內求出最長的由數組中元素組成的連續序列的長度。

最直觀的就是排序之後掃一遍，但這種方式時間複雜度為O(nlogn)，明顯不符合要求。

假設我們碰到一個數i，要求包含這個數的連續序列的長度

我們會去向左找i-1、i-2、i-3…是否在數組中，再向右找i+1、i+2、i+3…是否在序列中，直到找到第一個不在數組中的為止，然後即可知道i所在序列的長度。

因此我們可以利用hash表，先將數組中所有數存到hash表中，然後對數組中的數掃一遍，每個數依次為中心向左向右檢查是否在hash表中，直到掃到第一個不在hash表中的為止。

當然，如果要開始掃的時候，這個數之前已經檢查過了，那就無需再掃了，避免對一個連續序列重複掃描。

這裡hash表用unordered_map實現，時間複雜度為O(n)+O(n*hash表掃描效率)，這裡hash表掃描效率可以近似看成O(1)。

算法的關鍵點在於能否保證所有連續序列都正確掃描一遍。

因為每個數都會在一個連續序列中，因此每個連續序列是可以保證都檢查一遍的，向左向右一個一個檢查也不會將長度算錯，因此上述算法是正確的。

下面舉一個簡單例子走一遍算法幫助理解：[100,4,200,1,3,2]。


初始化：ans=0，將100、4、200、1、3、2扔到unordered_map中，是否掃描的狀態記為false；

掃描第一個數100:，還未掃描，向左：99不在unordered_map中，向右：101不在unordered_map中，ans=max(ans,101-99-1)=1；

掃描第二個數4，還未掃描，向左：3、2、1在unordered_map中0不在unordered_map中，向右：5不在unordered_map中，ans=max(ans,5-0-1)=4；

掃描第三個數200，已經掃描，跳過；

掃描第四個數1，已經掃描，跳過；

掃描第五個數3，已經掃描，跳過；

掃描第六個數2，已經掃描，跳過；

最終結果為ans=4。

int longestConsecutive(vector& nums)
{

int ans=0;
int len=nums.size();
unordered_map<int,bool> used;
for(int i=0;i<len;i++)
{
    used[nums[i]]=false;
}
for(int i=0;i<len;i++)
{
    if(used[nums[i]])continue;
    used[nums[i]]=true;
    int left=nums[i]-1,right=nums[i]+1;
    while(used.find(left)!=used.end())
    {
        used[left]=true;
        left--;
    }
    while(used.find(right)!=used.end())
    {
        used[right]=true;
        right++;
    }
    ans=max(ans,right-left-1);
}
return ans;
}

作者：東大ACM退役隊伍

編輯：劉凱旋

推薦閱讀：

leetcode刷題指南之WordLadderII

leetcode刷題指南之Triangle

leetcode刷題指南之Best Time to Buy and Sell Stock

相關焦點

  • leetcode刷題指南之RussianDollEnvelopes
    j].second)15                dp[i]=max(dp[i],dp[j]+1);16    int ans=0;17    for(int i=0;i<n;i++)18        ans=max(ans,dp[i]);19    return ans;20}21};推薦閱讀：leetcode
  • leetcode刷題指南之PatchingArray
    +]; 9        else{10            ans++;11            sum += sum+1;12        }13    }14    return ans;15}16};作者：東大ACM退役隊伍編輯：劉凱旋推薦閱讀：leetcode
  • leetcode刷題指南之shortestPalindrome
    i+1;18        }19    }20    for (int i = len; i < n; i++) {21        s += h[i];22    }23    return s;24}25};作者：東大ACM退役隊伍編輯：劉凱旋推薦閱讀：leetcode
  • leetcode刷題指南之PalindromePairs
    方法一：暴力枚舉(i, j)，判斷words[i]+words[j]是否是回文串。時間複雜度為O(n^2*k)。方法二：將所有字符串逆序插入map。對於每個字符串s，枚舉分割點pos，滿足[pos ~ s.size()-1]是回文串，且[0 ~ pos-1]的逆串在map中存在。
  • [LeetCode] 1027. Longest Arithmetic Subsequence 最長的等差數列
    < i_k <= A.length - 1, and that a sequence B is arithmetic if B[i+1] - B[i] are all the same value (for 0 <= i < B.length - 1).
  • leetcode刷題最強指南(版本1.0)
    為什麼會有這篇刷題指南很多剛開始刷題的同學都有一個困惑：面對leetcode上近兩千道題目，從何刷起
  • leetcode刷題指南之findtheduplicatenumber
    給出一個長度為n+1的數組，其中每個數字的範圍是[1,n]，其中只有一個重複的數，現在要求找出這個重複的數，並且滿足以下條件：不能改動原始數組除了原始數組，只能另外開闢O(1)的空間算法複雜度一定要小於O(n^2)重複的那個數可能重複不止一次初看這題可能有很多種方式
  • 【SQL刷題系列】:leetcode180 Consecutive Numbers
    點擊上方 ↑ 藍色關注「Python數據科學」SQL刷題系列：SQL作為一種資料庫查詢和程序設計語言，是從事數據技術人員必備的技能，也是各大公司的數據分析、數據挖掘、資料庫等筆試題必考的一種題。所以，不論大家是轉行還是學習都少不了這一關。為此，Python數據科學開啟了SQL刷題的系列，希望可以幫助有需要的朋友們。
  • 網際網路大廠算法面試題集合,看完我跪了!
    >leetcode 題解，記錄自己的 leetcode 解題之路。本倉庫目前分為五個部分：第一個部分是 leetcode 經典題目的解析，包括思路，關鍵點和具體的代碼實現。第二部分是對於數據結構與算法的總結第三部分是 anki 卡片， 將 leetcode 題目按照一定的方式記錄在 anki 中，方便大家記憶。
  • 網際網路公司最常見的面試算法題大集合!
    很多求職者都會在LeetCode刷上一遍，面試官也喜歡在上面挑選各類題目。LeetCode是一個美國的在線編程網站，收集了各個大廠的筆試面試題，對找工作的畢業生和開發者來說，非常有價值。不過LeetCode上面的題目很多都是考察應聘者對基礎知識的應用，適合進行練習編程基礎或者準備面試。很多求職者都會在LeetCode刷上一遍，面試官也喜歡在上面挑選各類題目。
  • 網際網路公司最常見的面試算法題大集合
    很多求職者都會在LeetCode刷上一遍，面試官也喜歡在上面挑選各類題目。LeetCode是一個美國的在線編程網站，收集了各個大廠的筆試面試題，對找工作的畢業生和開發者來說，非常有價值。不過LeetCode上面的題目很多都是考察應聘者對基礎知識的應用，適合進行練習編程基礎或者準備面試。很多求職者都會在LeetCode刷上一遍，面試官也喜歡在上面挑選各類題目。
  • [每日一題]14. Longest Common Prefix
    Write a function to find the longest common prefix string amongst an array
  • LeetCode 系列 第5題
    刷題地址: https://leetcode.com/problems/longest-palindromic-substring/簡單描述:Given a string s, return the longest palindromic substring
  • LeetCode-14. Longest Common Prefix | 最長公共前綴
    題目LeetCode[1]LeetCode-cn[2]Write a function to find the longest
  • 網際網路公司最常見的面試算法題大集合!
    來源：新智元LeetCode是一個美國的在線編程網站，收集了各個大廠的筆試面試題，對找工作的畢業生和開發者來說
  • leetcode每日一題:49.字母異位詞分組
    leetcode每日一題：49.字母異位詞分組：https://leetcode-cn.com/problems/group-anagrams/一起刷題吧一、題意分析 輸入：由字符串組成的列表（數組）輸出：將由同樣的字母和字母個數組成的不同序列放在一個列表裡，然後整體做為一個列表輸出難度
  • Leetcode刷題-動態規劃
    本文對leetcode上部分動態規劃問題進行分析並用python實現5. 最長回文子串 題目描述給定一個字符串 s，找到 s 中最長的回文子串。你可以假設 s 的最大長度為 1000。整體代碼結構也是與第五題的動態規劃代碼類似。
  • 笨方法刷 leetcode(一)
    ）本篇記錄5道題的解題思路，可能都是最笨的方法示例 2：輸入: s = "abc"輸出: true限制：0 <= len(s) <= 100原題連結：https://leetcode-cn.com/problems/is-unique-lcci/解決思路：
  • [LeetCode] 1143. Longest Common Subsequence 最長公共子序列
    Constraints:這道題讓求最長相同的子序列，注意是子序列，不是子串，所以字符並不需要相連，但是字符順序還是需要保持的。LeetCode 之前也有題目需要藉助求 LCS 來解題，比如 Delete Operation for Two Strings，當時博主還疑惑怎麼 LeetCode 中沒有專門求 LCS 的題呢，這不，終於補上了。
  • LeetCode 刷題指南(一):為什麼要刷題
    作者：數據結構與算法原文連結：selfboot.cn/2016/07/24/leetcode_guide_why/前言雖然刷題一直飽受詬病，不過不可否認刷題確實能鍛鍊我們的編程能力