2021年9月20日 星期一

[LeetCode] 128. Longest Consecutive Sequence

 轉自LeetCode

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

You must write an algorithm that runs in O(n) time.

 

Example 1:

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

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

 

Constraints:

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109
Solution


題目是要找到在一個 array 中,連續數字的最長長度

一開始想用sliding window,但題目的 array 不是 sorted 的,看起來不可行

題目又要求 O(n) 的時間複雜度

能加速歷遍速度的,看起來要用到 hash map or hash set

這邊選擇使用 hash set,可以直接把重複數字的變因消除掉

然後因為從 4 往下找到 1,也就是 4 -> 3 -> 2 -> 1

和從 1 找到 4,也就是 1 -> 2 -> 3 -> 4,兩者是一樣的

所以一旦有找過,就可以移除掉

因此,每個數字,我們就往上和往下找,一旦在 set 裡面,移除並移動指標

過程中也記錄最大值

Kotlin

沒有留言:

張貼留言