算法题--最长连续递增子序列长度
2020-05-06 本文已影响0人
岁月如歌2020
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: 利用集合+揪线头法
- 基本思路是:
- 先将数字存入集合
num_set中 - 遍历每个数字
num, 判断它是否是线头(即num - 1不在num_set中), 如果不是线头, 则略过, 若是线头, 则从它开始, 揪出以它开头的整根线，算出长度
- 分析:
- 在构建集合的过程中, 每个数字被遍历1次
- 在找线头的过程中，每个数字最多被遍历2次, 最少被遍历1次
- 因此, 每个数字最多被遍历3次，最少被遍历2次
- 复杂度
- 时间复杂度
O(N) - 空间复杂度
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])
输出结果
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. 结果
image.png
