Почему мое решение O(nlogn) быстрее, чем решение O(n) ⇐ Python

[Anonymous]

вот мое решение проблемы «самой длинной последовательной последовательности» в литкоде:

Код: Выделить всё

class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
if len(nums) == 0:
return 0
streaks = []
dums = sorted(set(nums))
longest = 1

for i in range(len(dums)):
if dums[i] == (dums[(i-1)] + 1):
longest += 1
else:
streaks.append(longest)
longest = 1

streaks.append(longest)

return max(streaks)

он ​​работает за 35 мс
и вот оптимальное решение для Neetcode, оно работает примерно за 52 мс

Код: Выделить всё

class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
nset = set(nums)
longest = 0

for n in nset:
if (n - 1) not in nset:
length = 0
while (n + length) in nset:
length += 1
longest = max(length, longest)
return longest

в чем причина

Подробнее здесь: https://stackoverflow.com/questions/798 ... n-solution