題目在此 128. Longest Consecutive Sequence
給一個數列，請計算出最長連續子序列的長度
請實作出 time complexity O(n) 的演算法
解題思維
我覺得這題非常有趣，當初也是撞牆了不少次
這題關鍵是每個數字判斷一次就好，所以當我們看到一個數字，就可以左邊右邊延伸看看
看看可以延伸到多長
看過的數字就可以丟掉了
程式碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
if (size := len(nums)) <= 1:
return size
nums = set(nums)
result = 0
while nums:
n = nums.pop()
left_count = 1
while n - left_count in nums:
nums.remove(n - left_count)
left_count += 1
right_count = 1
while n + right_count in nums:
nums.remove(n + right_count)
right_count += 1
result = max(result, left_count + right_count - 1)
return result
|
也許你也會想看看