Задача Leetcode: самая длинная последовательность
Задача:
Задав несортированный массив целых чисел nums, вернуть длину самой длинной последовательности элементов.
Вы должны написать алгоритм, который выполняется за время O(n).
Шаблон: Массивы и хэширование
Подход:
- Создайте набор для хранения элементов.
- Получить начало последовательности. Начало последовательности не имеет левого соседа.
- Как только мы определим начало последовательности, мы можем проверить, существует ли следующее значение в наборе.
- Следить за длиной последовательности.
- Вернуть максимальную длину.
Нотация Big-O:
Временная сложность: O(n)
Мы выполняем итерации n раз для каждого элемента.
Сложность пространства: O(n)
Мы используем структуру данных Set для хранения n элементов.
Код:
class Solution {
public int longestConsecutive(int[] nums) {
// use hashset to store n values
Set <Integer> hashSet = new HashSet<>();
// maxLength to keep track of longest consecutive sequence
int maxLength = Integer.MIN_VALUE;
// edge case
if (nums.length == 0 || nums.length == 1){
return nums.length;
}
// add all elements into hashset
for(int i : nums){
hashSet.add(i);
}
// get the first sequence
for(int curr : nums){
// does left exist in hashMap
// if it does not then it is the start of a sequence
if(!hashSet.contains(curr - 1)){
int count = 1;
boolean flag = true;
while(flag == true){
if(hashSet.contains(curr + 1)){
count++;
curr++;
} else {
flag = false;
}
maxLength = Math.max(maxLength, count);
}
}
}
return maxLength;
}
}