資訊專欄INFORMATION COLUMN
摘要：集合法復(fù)雜度時(shí)間空間思路將所有數(shù)都加入集合中，然后再遍歷這些數(shù)，因?yàn)槲覀兡艿呐袛嗄硞€(gè)數(shù)是否在集合中，所以我們可以一個(gè)個(gè)向上或者向下檢查。時(shí)間復(fù)雜度仍是，因?yàn)槲覀儾粫?huì)檢查不存在于數(shù)組的數(shù)，而存在于數(shù)組的數(shù)也只會(huì)檢查一次。
Longest Consecutive Sequence
排序法 復(fù)雜度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.
時(shí)間 O(NlogN) 空間 O(1)
思路將數(shù)組排序后，從前向后遍歷，找到最長(zhǎng)的連續(xù)部分，該方法隨不符合題意，但是不用空間。
集合法 復(fù)雜度時(shí)間 O(N) 空間 O(N)
思路將所有數(shù)都加入集合中，然后再遍歷這些數(shù)，因?yàn)槲覀兡躉(1)的判斷某個(gè)數(shù)是否在集合中，所以我們可以一個(gè)個(gè)向上或者向下檢查。為了避免之后重復(fù)檢查，我們每查到一個(gè)數(shù)，都要將其從集合中移除。這樣每遇到一個(gè)數(shù)，都檢查它的上下邊界，就能找出最長(zhǎng)的連續(xù)數(shù)列。時(shí)間復(fù)雜度仍是O(N)，因?yàn)槲覀儾粫?huì)檢查不存在于數(shù)組的數(shù)，而存在于數(shù)組的數(shù)也只會(huì)檢查一次。
代碼public class Solution {
public int longestConsecutive(int[] nums) {
int maxlen = 0;
Set set = new HashSet();
// 先將所有數(shù)字加入數(shù)組中
for(int n : nums){
set.add(n);
}
// 對(duì)于每個(gè)數(shù)我們都在集合中一一檢查它的上下邊界
for(int n : nums){
// 暫存n，供檢查下邊界時(shí)使用
int curr = n, len = 0;
// 一個(gè)一個(gè)檢查上邊界
while(set.contains(curr)){
curr++;
len++;
set.remove(curr);
}
// 一個(gè)一個(gè)檢查下邊界
curr = n - 1;
while(set.contains(curr)){
curr--;
len++;
set.remove(curr);
}
maxlen = Math.max(len, maxlen);
}
return maxlen;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/64610.html
摘要：遞歸法復(fù)雜度時(shí)間空間思路因?yàn)橐易铋L(zhǎng)的連續(xù)路徑，我們?cè)诒闅v樹的時(shí)候需要兩個(gè)信息，一是目前連起來的路徑有多長(zhǎng)，二是目前路徑的上一個(gè)節(jié)點(diǎn)的值。代碼判斷當(dāng)前是否連續(xù)返回當(dāng)前長(zhǎng)度，左子樹長(zhǎng)度，和右子樹長(zhǎng)度中較大的那個(gè) Binary Tree Longest Consecutive Sequence Given a binary tree, find the length of the lon...
摘要：描述例子要求分析從未排序的數(shù)組中尋找最長(zhǎng)的連續(xù)的數(shù)字，必然要循環(huán)一遍所有的數(shù)字，因?yàn)檫B續(xù)，所以以出來的數(shù)字為基準(zhǔn)，向左右擴(kuò)散，直到?jīng)]有連續(xù)的，利用了和的特性。 描述： Given an unsorted array of integers, find the length of the longest consecutive elements sequence. 例子： Given ...
摘要：先排序，然后用數(shù)組記錄每一位上連續(xù)序列的長(zhǎng)度，每次循環(huán)更新最大值存為。 Problem Given an unsorted array of integers, find the length of the longest consecutive elements sequence. Clarification Your algorithm should run in O(n) com...
Problem Given a binary tree, you need to find the length of Longest Consecutive Path in Binary Tree. Especially, this path can be either increasing or decreasing. For example, [1,2,3,4] and [4,3,2,1] ...
摘要：在線網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號(hào)： showImg(htt...
閱讀 3713·2021-11-11 16:55
閱讀 1655·2021-10-08 10:04
閱讀 3590·2021-09-27 13:36
閱讀 2784·2019-08-30 15:53
閱讀 1870·2019-08-30 11:17
閱讀 1272·2019-08-29 16:55
閱讀 2111·2019-08-29 13:57
閱讀 2526·2019-08-29 13:13
