目錄
- 1、題目
- 2、思路
- 3、c++代碼
- 4、java代碼
1、題目
給定一個未排序的整數陣列 nums ，找出數字連續的最長序列（不要求序列元素在原陣列中連續）的長度，
請你設計并實作時間復雜度為 O(n) 的演算法解決此問題，
示例 1：
輸入：nums = [100,4,200,1,3,2]
輸出：4
解釋：最長數字連續序列是 [1, 2, 3, 4]，它的長度為 4，
示例 2：
輸入：nums = [0,3,7,2,5,8,4,6,0,1]
輸出：9
提示：
0 <= nums.length <= 105-109 <= nums[i] <= 109
2、思路
(哈希） O ( n ) O(n) O(n)
在一個未排序的整數陣列 nums中 ，找出最長的數字連續序列，樸素的做法是：列舉nums中的每一個數x，并以x起點，在nums陣列中查詢x + 1,x + 2，，，x + y是否存在，假設查詢到了 x + y，那么長度即為 y - x + 1，不斷列舉更新答案即可，
如果每次查詢一個數都要遍歷一遍nums陣列的話，時間復雜度為
O
(
n
)
O(n)
O(n) ，其實我們可以用一個哈希表來存貯陣列中的數，這樣查詢的時間就能優化為
O
(
1
)
O(1)
O(1) ，
為了保證
O
(
n
)
O(n)
O(n)的時間復雜度，避免重復列舉一段序列，我們要從序列的起始數字向后列舉，也就是說如果有一個x, x+1, x+2, x+y的連續序列，我們只會以x為起點向后列舉，而不會從x+1,x+2,向后列舉，
如何每次只列舉連續序列的起始數字x？
其實只需要每次在哈希表中檢查是否存在 x?1即可，如果x-1存在，說明當前數x不是連續序列的起始數字，我們跳過這個數，
具體程序如下：
- 1、定義一個哈希表
hash，將nums陣列中的數都放入哈希表中， - 2、遍歷哈希表
hash，如果當前數x的前驅x-1不存在，我們就以當前數x為起點向后列舉， - 3、假設最長列舉到了數
y，那么連續序列長度即為y-x+1， - 4、不斷列舉更新答案，
時間復雜度分析： while回圈最多執行
n
n
n次，因此時間復雜度為
O
(
n
)
O(n)
O(n) ，
3、c++代碼
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_set<int> hash;
for(auto x : nums) hash.insert(x); //放入hash表中
int res = 0;
for(auto x : hash)
{
if(hash.count(x) && !hash.count(x-1))
{
int y = x; //以當前數x向后列舉
while(hash.count(y + 1)) y++;
res = max(res, y - x + 1); //更新答案
}
}
return res;
}
};
4、java代碼
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> hash = new HashSet<Integer>();
for(int x : nums) hash.add(x); //放入hash表中
int res = 0;
for(int x : hash)
{
if(hash.contains(x) && !hash.contains(x-1))
{
int y = x; //以當前數x向后列舉
while(hash.contains(y + 1)) y++;
res = Math.max(res, y - x + 1); //更新答案
}
}
return res;
}
}
原文鏈接： 128. 最長連續序列
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/292483.html
標籤：java