Перейти к содержанию

Название задания

Ссылка с заданием на литкоде

Описание

Для полученного массива чисел nums необходимо вернуть длину самой длинной последовательности эллементов.

Алгоритм должен работать за \(O(n)\) времени.

Пример 1:

Входные данные: nums = [100, 4, 200, 1, 3, 2]
Выходные данные: 4
Объяснение: самая длинная последовательность [1, 2, 3, 4] имеет длину 4

Пример 2:

Входные данные: nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
Выходные данные: 9

Пример 3:

Входные данные: nums = [1, 2, 1, 1, 2, 400, 500, 1]
Выходные данные: 2

Идея решения

Первой идеей приходит отсортировать массив и найти самую длинную последовательность перебирая его. Ограничение в \(O(n)\) не позволяет нам использовать сортировку, необходимо использовать другой подход. Условно нам необходимо разделить полученый массив на последовательности и затем найти самую длинную из них. Для примера [100, 4, 200, 1, 3, 2] это будет три последовательности {1, 2, 3, 4}, {100}, {200}.

Стоит отметить, что последовательностью будет только [num, num + 1, num + 2, ...], увеличение эллементов происходит ровно на 1. Кроме того, \(O(n)\) не означает, что мы можем пройти по массиву лишь один раз, \(O(3n)\) сокращается до \(O(n)\).

Алгоритм решения

Для быстрого доступа к элементам нам нужно преобразовать массив в множество. Среди всех полученых чисел нас интересуют только те числа, которые являются началом каждой отдельной последовательности. Другими словами, такие num, которые среди nums не имеют num - 1. Имея все "корни" последовательностей можно легко определить длину каждой и определить наибольшее значение.

Таким образом наш алгоритм выглядит так: 1. преобразуем массив nums в множество
2. определяем все начала последовательностей, то есть те num, для которых нет num - 1 среди nums
3. для каждого начала последовательности определяем как много есть чисел num + n, n + 1 будет длинной последовательности
4. обновляем значение streak, если текущая длина последовательности больше

Сложность

  • По времени: \(O(N)\) n = len(nums)

  • По памяти: \(O(N)\) n = len(nums)

Код решения:

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        nums = set(nums)
        roots = set()
        for num in nums:
            if num - 1 not in nums:
                roots.add(num)

        streak = 0
        for root in roots:
            c_streak = 0
            while root in nums:
                c_streak += 1
                root += 1
            streak = max(streak, c_streak)

        return streak

use std::collections::{HashMap, HashSet};

impl Solution {
    pub fn longest_consecutive(nums: Vec<i32>) -> i32 {
        let nums: HashSet<i32> = nums.into_iter().collect();
        let mut roots: HashSet<i32> = HashSet::new();

        for num in &nums {
            if !nums.contains(&(num - 1)) {
                roots.insert(*num);
            }
        }

        let mut streak = 0;
        for mut root in roots {
            let mut c_streak = 0;
            while nums.contains(&root) {
                c_streak += 1;
                root += 1;
            }
            streak = std::cmp::max(streak, c_streak);
        }
        streak
    }
}