專欄：50多種數(shù)據(jù)結(jié)構(gòu)徹底征服

專欄：50多種經(jīng)典圖論算法全部掌握

一網(wǎng)友發(fā)文稱：因為簽了華為，過年的時候親戚都問華為能開多少錢，還讓弟弟妹妹們向我學習，夸我媽我爸養(yǎng)了個好孩子，說從小就知道我這個人以后一定有出息，被夸的都快上天了。進華為對于老家人來說原來這么有面子。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第128題：最長連續(xù)序列。

問題描述

來源：LeetCode第128題

難度：中等

給定一個未排序的整數(shù)數(shù)組 nums ，找出數(shù)字連續(xù)的最長序列（不要求序列元素在原數(shù)組中連續(xù)）的長度。請你設(shè)計并實現(xiàn) 時間復(fù)雜度為 O(n) 的算法解決此問題。

示例1：

輸入：nums = [100,4,200,1,3,2] 輸出：4 解釋：最長數(shù)字連續(xù)序列是 [1, 2, 3, 4]。它的長度為 4。

示例2：

輸入：nums = [0,3,7,2,5,8,4,6,0,1] 輸出：9

• 0 <= nums.length <= 10^5

• -10^9 <= nums[i] <= 10^9

問題分析

這題讓找出 數(shù)字連續(xù)的最長序列 ，我們很容易想到先對數(shù)組進行排序，然后查找，但題中要求時間復(fù)雜度是 O(n) ，排序的時間復(fù)雜度最低也是 O(nlogn) ，不符合要求。

數(shù)字連續(xù)的序列肯定有個 起始值 ，我們只需要從起始值開始查找即可，比如序列[3,2,4,1]，比數(shù)字 3 小的有 2 ，所以 3 肯定不是連續(xù)序列的起始值，同理數(shù)字 2,4 也都不是，只有數(shù)字 1 是起始值，因為數(shù)字 1 前面沒有數(shù)字 0 ，所以只需要從數(shù)字 1 開始查找即可。

也就是說如果當前數(shù)字前面還有相鄰的數(shù)字，那么當前數(shù)字就不可能是起始值，這里怎么判斷當前數(shù)字前面還有沒有相鄰的數(shù)字呢？我們可以提前把數(shù)組中的元素全部放到集合set中，判斷的時候只需要從set中查找即可。

JAVA：

public int longestConsecutive(int[] nums) {     Set
           
           
  set =  new HashSet<>();      for ( int num : nums)         set.add(num); // 元素存儲到集合set中      int maxLen =  0;      for ( int num : nums) {          if (!set.contains(num -  1)) { // 判斷是否是起始位置              int curNum = num;              // 從起始位置開始查找連續(xù)序列的長度              int len =  1;              while (set.contains(curNum +  1)) {                 curNum++;                 len++;             }             maxLen = Math.max(maxLen, len);         }     }      return maxLen; }

C++：

public:     int longestConsecutive(vector

  &nums) {         unordered_set

  mySet;         for (const int &num: nums)             mySet.insert(num);// 元素存儲到集合set中         int maxLen = 0;         for (const int &num: mySet) {             if (!mySet.count(num - 1)) {// 判斷是否是起始位置                 int curNum = num + 1;                 int len = 1;                 // 從起始位置開始查找連續(xù)序列的長度                 while (mySet.count(curNum)) {                     curNum++;                     len++;                 }                 maxLen = max(maxLen, len);             }         }         return maxLen;     }

Python：

def longestConsecutive(self, nums: List[int]) -> int:     mySet = set(nums)     maxLen = 0     for num in nums:         if num - 1 not in mySet:  # 判斷是否是起始位置             curNum = num  # 從起始位置開始查找連續(xù)序列的長度             len = 1             while curNum + 1 in mySet:                 curNum += 1                 len += 1             maxLen = max(maxLen, len)     return maxLen

筆者簡介

博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數(shù)據(jù)結(jié)構(gòu)和算法 的講解，在全球30多個算法網(wǎng)站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關(guān)注，也可以 下載我整理的1000多頁的PDF算法文檔 。