sc/Все задачи

Самая длинная последовательная последовательность

СредняяМассивы и Хешированиеlongest-consecutive-sequence

Дан массив целых чисел nums. Верните длину самой длинной последовательной последовательности элементов, которую можно сформировать.

Последовательная последовательность - это последовательность элементов, в которой каждый элемент ровно на 1 больше предыдущего. Элементы не обязательно должны быть последовательными в исходном массиве.

Вы должны написать алгоритм, который работает за время O(n).

Пример 1:

Input: nums = [2,20,4,10,3,4,5]

Output: 4
Объяснение: Самая длинная последовательная последовательность - [2,3,4,5].

Пример 2:

Input: nums = [0,3,2,5,4,6,1,1]

Output: 7

Рекомендуемая временная и пространственная сложность

Вам следует стремиться к решению с временной сложностью O(n) и пространственной сложностью O(n), где n — размер входного массива.

Подсказка 1

Сортировка массива даст вам O(n log n) решение. Как можно достичь O(n)?

Подсказка 2

Используйте хеш-множество для мгновенного поиска чисел. Для каждого числа проверяйте, существует ли число на единицу больше.

Подсказка 3

Оптимизируйте поиск, начиная только с чисел, которые могут быть началом последовательности (т.е. когда число на единицу меньше не существует в множестве).

JavaScript

class Solution {
    // Подход с Set
    longestConsecutive(nums) {
        if (!nums.length) return 0;
        const set = new Set(nums);
        let maxStreak = 0;
        
        for (let num of nums) {
            // Проверяем, является ли число началом последовательности
            if (!set.has(num - 1)) {
                let currentNum = num;
                let currentStreak = 1;
                
                while (set.has(currentNum + 1)) {
                    currentNum++;
                    currentStreak++;
                }
                
                maxStreak = Math.max(maxStreak, currentStreak);
            }
        }
        
        return maxStreak;
    }
    // Время: O(n), Память: O(n)
    
    // Подход с сортировкой
    longestConsecutiveSort(nums) {
        if (!nums.length) return 0;
        nums.sort((a, b) => a - b);
        
        let maxStreak = 1;
        let currentStreak = 1;
        
        for (let i = 1; i < nums.length; i++) {
            if (nums[i] !== nums[i-1]) {
                if (nums[i] === nums[i-1] + 1) {
                    currentStreak++;
                } else {
                    maxStreak = Math.max(maxStreak, currentStreak);
                    currentStreak = 1;
                }
            }
        }
        
        return Math.max(maxStreak, currentStreak);
    }
    // Время: O(n log n), Память: O(1)
}

Java

class Solution {
    // Подход с HashSet
    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) return 0;
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        
        int maxStreak = 0;
        
        for (int num : nums) {
            if (!set.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;
                
                while (set.contains(currentNum + 1)) {
                    currentNum++;
                    currentStreak++;
                }
                
                maxStreak = Math.max(maxStreak, currentStreak);
            }
        }
        
        return maxStreak;
    }
    // Время: O(n), Память: O(n)
    
    // Подход с сортировкой
    public int longestConsecutiveSort(int[] nums) {
        if (nums.length == 0) return 0;
        Arrays.sort(nums);
        
        int maxStreak = 1;
        int currentStreak = 1;
        
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i-1]) {
                if (nums[i] == nums[i-1] + 1) {
                    currentStreak++;
                } else {
                    maxStreak = Math.max(maxStreak, currentStreak);
                    currentStreak = 1;
                }
            }
        }
        
        return Math.max(maxStreak, currentStreak);
    }
    // Время: O(n log n), Память: O(1)
}

Python

class Solution:
    # Подход с set
    def longestConsecutive(self, nums: List[int]) -> int:
        if not nums:
            return 0
            
        num_set = set(nums)
        max_streak = 0
        
        for num in nums:
            if num - 1 not in num_set:
                current_num = num
                current_streak = 1
                
                while current_num + 1 in num_set:
                    current_num += 1
                    current_streak += 1
                
                max_streak = max(max_streak, current_streak)
                
        return max_streak
    # Время: O(n), Память: O(n)
    
    # Подход с сортировкой
    def longestConsecutive_sort(self, nums: List[int]) -> int:
        if not nums:
            return 0
            
        nums.sort()
        max_streak = 1
        current_streak = 1
        
        for i in range(1, len(nums)):
            if nums[i] != nums[i-1]:
                if nums[i] == nums[i-1] + 1:
                    current_streak += 1
                else:
                    max_streak = max(max_streak, current_streak)
                    current_streak = 1
                    
        return max(max_streak, current_streak)
    # Время: O(n log n), Память: O(1)

solution.js · сохранено

Входные данные

[2,20,4,10,3,4,5]

Ожидаемый результат