Início / user-8622814

Samson's questions

Martin Hope
Samson
Asked: 2025-04-02 16:28:26 +0800 CST
  • 6

Eu estava tentando resolver a questão 128 do LeetCode. Maior sequência consecutiva :

Dado um array não classificado de inteiros nums, retorne o comprimento da maior sequência de elementos consecutivos .

Você deve escrever um algoritmo que seja executado no O(n)tempo.

Exemplo 1:

Entrada: nums = [100,4,200,1,3,2]
Saída: 4
Explicação: A sequência de elementos consecutivos mais longa é [1, 2, 3, 4]. Portanto, seu comprimento é 4.

Restrições:

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109

Minha primeira tentativa fez classificação seguida de contagem. Isso tem complexidade de tempo O(nlogn), mas surpreendentemente me deu 93,93% de percentil para complexidade de tempo (40ms).

Então reli a questão e percebi que a resposta deve estar em complexidade de tempo O(n). Então escrevi o seguinte código:

def longestConsecutive(self, nums: List[int]) -> int:
        s = set(nums)
        longest_streak = 0
        
        for num in nums:
            if (num - 1) not in s:
                current_streak = 1
                while (num + 1) in s:
                    num += 1
                    current_streak += 1
                longest_streak = max(longest_streak, current_streak)
            
        return longest_streak

(Eu sei, não é uma boa prática reutilizar o nome da variável num no loop aninhado, mas isso não vem ao caso. Eu testei usando uma variável separada também com o mesmo resultado abaixo)

Embora isso devesse teoricamente ter complexidade de tempo O(n), mais rápido que minha primeira solução, isso na verdade resultou em limite de tempo excedido para alguns casos e meu código foi rejeitado.

Acabei enviando uma solução de aprovação após consultar a solução

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        nums = set(nums)
        longest_streak = 0
        
        for num in nums:
            if (num - 1) not in nums:
                next_num = num + 1
                while next_num in nums:
                    next_num += 1
                longest_streak = max(longest_streak, next_num - num)
            
        return longest_streak

onde identifiquei 2 diferenças principais:

  1. Reatribuí nums a um conjunto no local em vez de uma nova variável
  2. Usei next_num em vez de manter uma variável current_streak

No entanto, ambas as mudanças não parecem ter impacto significativo no tempo de execução, o suficiente para cruzar a linha entre o limite de tempo excedido e uma solução de passagem. Para me confundir ainda mais, essa solução O(n) ainda teve um desempenho pior do que minha solução de classificação, classificando-se apenas no percentil 75,73% (46 ms).

Então minhas perguntas são:

  1. Por que um algoritmo O(nlogn) tem desempenho mais rápido que O(n) na prática?
  2. Por que meu primeiro algoritmo O(n) é tão lento que atingiu o limite de tempo excedido, enquanto meu segundo algoritmo com alterações mínimas conseguiu passar?
python