C/C++ | LeetCode
Задача: 128. Longest Consecutive Sequence
Сложность: medium
Найти длину самой длинной последовательности последовательных чисел в неотсортированном массиве. Время работы — O(n).
Пример:
Input: [100,4,200,1,3,2] → Output: 4
👨💻 Алгоритм:
1⃣Помещаем все числа в unordered_set, чтобы можно было быстро проверять наличие элемента (O(1) время доступа).
2⃣Проходим по каждому числу, и если num - 1 не существует в сете — это начало новой последовательности. Затем увеличиваем currentNum, пока currentNum + 1 есть в сете, считая длину последовательности.
3⃣После проверки каждого числа обновляем longestStreak, если текущая последовательность длиннее.
😎 Решение:
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_set<int> numSet(nums.begin(), nums.end());
int longestStreak = 0;
for (int num : numSet) {
if (!numSet.count(num - 1)) {
int currentNum = num;
int currentStreak = 1;
while (numSet.count(currentNum + 1)) {
currentNum++;
currentStreak++;
}
longestStreak = max(longestStreak, currentStreak);
}
}
return longestStreak;
}
};
Ставь 👍 и забирай 📚 Базу знаний
1 · 258 ·