C# | LeetCode

Задача: 128. Longest Consecutive Sequence
Сложность: medium

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

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

Пример:

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.

👨‍💻

Алгоритм:

1⃣Проверка базового случая:
Перед началом работы проверяем базовый случай с пустым массивом.
Самая длинная последовательность в пустом массиве, очевидно, равна 0, поэтому мы можем просто вернуть это значение.

2⃣Обработка чисел в массиве:
Для всех других случаев мы сортируем массив nums и рассматриваем каждое число, начиная со второго (поскольку нам нужно сравнивать каждое число с предыдущим).
Если текущее число и предыдущее равны, то текущая последовательность не удлиняется и не прерывается, поэтому мы просто переходим к следующему числу.
Если числа не равны, то нужно проверить, удлиняет ли текущее число последовательность (т.е. nums[i] == nums[i-1] + 1). Если удлиняет, то мы увеличиваем наш текущий счёт и продолжаем.

3⃣Завершение обработки и возврат результата:
В противном случае последовательность прерывается, и мы записываем нашу текущую последовательность и сбрасываем её до 1 (чтобы включить число, которое прервало последовательность).
Возможно, что последний элемент массива nums является частью самой длинной последовательности, поэтому мы возвращаем максимум из текущей последовательности и самой длинной.

😎

Решение:

public class Solution {
    private bool ArrayContains(int[] arr, int num) {
        for (int i = 0; i < arr.Length; i++) {
            if (arr[i] == num) {
                return true;
            }
        }

        return false;
    }

    public int LongestConsecutive(int[] nums) {
        int longestStreak = 0;
        for (int i = 0; i < nums.Length; i++) {
            int currentNum = nums[i];
            int currentStreak = 1;
            while (ArrayContains(nums, currentNum + 1)) {
                currentNum += 1;
                currentStreak += 1;
            }

            longestStreak = Math.Max(longestStreak, currentStreak);
        }

        return longestStreak;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Please open Telegram to view this post