Leetcode 128 Longest Consecutive Sequence

Soru

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Örnek 1

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Örnek 2

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

Çözüm

• Verilen bir tam sayı dizisindeki en uzun ardışık eleman dizisini bulmanızı gerektiren bir problem. Bu sorun, elemanların dizide sıralı olarak verilmediği durumlarda da ardışık sayı dizisini etkin bir şekilde tespit etmeyi amaçlar.
• Bu problemi çözmek için en etkili yöntem, bir set kullanmaktır. Set yapısı, herhangi bir elemanın mevcut olup olmadığını O(1) zaman karmaşıklığında kontrol etmenize olanak tanır.
• Algoritma Adımları:
• Tüm elemanları bir set içine yerleştirin.
• Dizi üzerinde döngü yaparak, her eleman için, bu elemanın ardışık dizinin başlangıcı olup olmadığını kontrol edin. Bir elemanın ardışık dizinin başlangıcı olması için, ondan bir eksik olan elemanın sette olmaması gerekir.
• Eğer eleman ardışık dizinin başlangıcıysa, bu elemandan itibaren ardışık olarak kaç eleman olduğunu sayın.
• En yüksek sayımı kaydedin.

Code

    def longestConsecutive(self, nums: List[int]) -> int:
            num_set = set(nums)
            longest_streak = 0
            for num in num_set:
                # Sadece ardışık dizinin başlangıç elemanı için işlem yap
                if num - 1 not in num_set:
                    current_num = num
                    current_streak = 1
                    while current_num + 1 in num_set:
                        current_num += 1
                        current_streak += 1
                    longest_streak = max(longest_streak, current_streak)
            return longest_streak

Complexity

• Time complexity (Zaman Karmaşıklığı): Her bir eleman için, ondan büyük ardışık elemanları aramak için set içinde kontrol yapılır. Ancak her eleman, ardışık dizi içinde sadece bir kez ziyaret edilir. Bu nedenle, toplam zaman karmaşıklığı ortalama O(n)‘dir.
• Space complexity (Alan Karmaşıklığı): Tüm elemanları saklamak için bir set kullanıldığı için alan karmaşıklığı O(n) olur.