算法題--最長(zhǎng)連續(xù)遞增子序列長(zhǎng)度

image.png

0. 鏈接

題目鏈接

1. 題目

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

Example:

Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

2. 思路1: 利用集合+揪線頭法

  1. 基本思路是:
  • 先將數(shù)字存入集合num_set
  • 遍歷每個(gè)數(shù)字num, 判斷它是否是線頭(即num - 1不在num_set中), 如果不是線頭, 則略過(guò), 若是線頭, 則從它開(kāi)始, 揪出以它開(kāi)頭的整根線排抬,算出長(zhǎng)度
  1. 分析:
  • 在構(gòu)建集合的過(guò)程中, 每個(gè)數(shù)字被遍歷1次
  • 在找線頭的過(guò)程中零酪,每個(gè)數(shù)字最多被遍歷2次, 最少被遍歷1次
  • 因此, 每個(gè)數(shù)字最多被遍歷3次损晤,最少被遍歷2次
  1. 復(fù)雜度
  • 時(shí)間復(fù)雜度 O(N)
  • 空間復(fù)雜度 O(N)

3. 代碼

# coding:utf8
from typing import List


class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        longest_streak = 0
        num_set = set(nums)
        for num in num_set:
            if num - 1 not in num_set:
                cur_num = num
                cur_streak = 1
                while cur_num + 1 in num_set:
                    cur_num += 1
                    cur_streak += 1
                longest_streak = max(longest_streak, cur_streak)
        return longest_streak


def my_test(solution, nums):
    print('input: {}; output: {}'.format(nums, solution.longestConsecutive(nums)))


solution = Solution()

my_test(solution, [100, 4, 200, 1, 3, 2])
my_test(solution, [0, 0, 1, -1])
my_test(solution, [0, 0])
my_test(solution, [0, 3, 7, 2, 5, 8, 4, 6, 0, 1])


輸出結(jié)果

input: [100, 4, 200, 1, 3, 2]; output: 4
input: [0, 0, 1, -1]; output: 3
input: [0, 0]; output: 1
input: [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]; output: 9

4. 結(jié)果

image.png
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末旨涝,一起剝皮案震驚了整個(gè)濱河市瘫寝,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌,老刑警劉巖屉来,帶你破解...
    沈念sama閱讀 222,807評(píng)論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件路翻,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡茄靠,警方通過(guò)查閱死者的電腦和手機(jī)茂契,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,284評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門(mén),熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)慨绳,“玉大人掉冶,你說(shuō)我怎么就攤上這事∑暄” “怎么了厌小?”我有些...
    開(kāi)封第一講書(shū)人閱讀 169,589評(píng)論 0 363
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)喂江。 經(jīng)常有香客問(wèn)我召锈,道長(zhǎng),這世上最難降的妖魔是什么获询? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 60,188評(píng)論 1 300
  • 正文 為了忘掉前任涨岁,我火速辦了婚禮,結(jié)果婚禮上吉嚣,老公的妹妹穿的比我還像新娘梢薪。我一直安慰自己,他們只是感情好尝哆,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,185評(píng)論 6 398
  • 文/花漫 我一把揭開(kāi)白布秉撇。 她就那樣靜靜地躺著,像睡著了一般秋泄。 火紅的嫁衣襯著肌膚如雪琐馆。 梳的紋絲不亂的頭發(fā)上,一...
    開(kāi)封第一講書(shū)人閱讀 52,785評(píng)論 1 314
  • 那天恒序,我揣著相機(jī)與錄音瘦麸,去河邊找鬼。 笑死歧胁,一個(gè)胖子當(dāng)著我的面吹牛滋饲,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播喊巍,決...
    沈念sama閱讀 41,220評(píng)論 3 423
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼屠缭,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來(lái)了崭参?” 一聲冷哼從身側(cè)響起呵曹,我...
    開(kāi)封第一講書(shū)人閱讀 40,167評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎,沒(méi)想到半個(gè)月后奄喂,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體之剧,經(jīng)...
    沈念sama閱讀 46,698評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,767評(píng)論 3 343
  • 正文 我和宋清朗相戀三年砍聊,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片贰军。...
    茶點(diǎn)故事閱讀 40,912評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡玻蝌,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出词疼,到底是詐尸還是另有隱情俯树,我是刑警寧澤,帶...
    沈念sama閱讀 36,572評(píng)論 5 351
  • 正文 年R本政府宣布贰盗,位于F島的核電站许饿,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏舵盈。R本人自食惡果不足惜陋率,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,254評(píng)論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望秽晚。 院中可真熱鬧瓦糟,春花似錦、人聲如沸赴蝇。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 32,746評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)句伶。三九已至劲蜻,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間考余,已是汗流浹背先嬉。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 33,859評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留秃殉,地道東北人坝初。 一個(gè)月前我還...
    沈念sama閱讀 49,359評(píng)論 3 379
  • 正文 我出身青樓,卻偏偏與公主長(zhǎng)得像钾军,于是被迫代替她去往敵國(guó)和親鳄袍。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,922評(píng)論 2 361