Leetcode 217 Contains Duplicate

Soru

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Örnek 1

Input: nums = [1,2,3,1]
Output: true

Örnek 2

Input: nums = [1,2,3,4]
Output: false

Örnek 3

Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true

Çözüm

• Bu çözümde, bir set yapısı kullanılıyor. set, Python’da benzersiz elemanları saklamak için kullanılan bir veri yapısıdır. Döngü içerisinde, dizideki her eleman kontrol ediliyor ve bu eleman daha önce set içerisine eklenmişse True döndürülüyor. Eğer döngü bitene kadar tekrar eden bir eleman bulunmazsa False döndürülür.

• Bu, problemi çözmek için etkili bir yöntemdir çünkü set yapısının ortama zaman karmaşıklığı O(1)’dir, bu da her bir elemanın varlığının hızlıca kontrol edilmesini sağlar. Bu çözüm, genelde O(n) zaman karmaşıklığına sahiptir, çünkü her eleman bir kez kontrol edilir.

Code

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        counter = set()
        
        for num in nums:
            if num not in counter:
                counter.add(num)
            else:
                return True
            
        return False

Complexity

• Time complexity : Bu çözümde for döngüsü dizideki her elemanı bir kez kontrol eder. Her iterasyonda, set yapısına eleman eklemek veya elemanın set içinde olup olmadığını kontrol etmek O(1) zamanda gerçekleşir. Bu durumda, n elemanlı bir dizi için toplam zaman karmaşıklığı O(n) olur. Burada n, dizinin uzunluğudur.

• Space complexity : Bu algoritma, gördüğü her elemanı bir set yapısında saklar. En kötü durumda, yani tüm elemanlar benzersiz olduğunda, bu set dizinin tüm elemanlarını saklayacak kapasiteye sahip olmalıdır. Bu durumda, alan karmaşıklığı O(n) olur, burada n yine dizinin uzunluğudur.