Учитывая несортированный массив целых чисел
nums
, вернуть длину самой длинной последовательности последовательных элементов.
Чтобы решить эту проблему, мы сохраняем текущий последовательный счетчик в dp[i].
Когда у нас есть отсортированный массив: [1, 3, 4, 4, 5], вывод равен 3. Поэтому мы хотим, чтобы dp[i] оставалось неизменным, когда sorted[i] равно sorted[i-1], в этом случай dp равен [1, 1, **2, 2**, 3].
И мы сбрасываем dp[i] в 1, если sorted[i]-sorted[i-1] не равен 0 или 1.
- Отсортируйте массив, чтобы убедиться, что число находится в порядке возрастания.
- Инициализировать параметры
- Перебрать отсортированный массив
* Если sorted[i]-sorted[i-1] равно 1 => dp[i] = dp[i-1] + 1 и обновить max, если dp[i] › original max
* else if sorted[i]-sorted[i-1] равно 0 => dp[i] = 1
* else dp[i] = 1 - Вернуть максимум
Временная сложность будет O(n log n), так как самая тяжелая из них сортирует массив.
Пространственная сложность будет O(n), поскольку у нас есть массив с одинаковой длиной входных чисел.
/** * @param {number[]} nums * @return {number} */ var longestConsecutive = function(nums) { if (nums.length === 0) return 0; let sorted = nums.sort((a, b)=>a-b); let max = 1; let dp = Array(nums.length); dp[0] = 1; for (let i = 1; i < nums.length; i++){ if (sorted[i]-sorted[i-1] === 1){ dp[i] = dp[i-1]+1; max = Math.max(max, dp[i]) } else if (sorted[i] === sorted[i-1]){ dp[i] = dp[i-1]; } else{ dp[i] = 1; } } return max; };