LeetCode Contains Duplicate Python Çözümü

Bu sayfada LeetCode sitesindeki “Contains Duplicate(217)” sorusunu Python diliyle nasıl verimli bir şekilde çözebileceğimizi ve gidilebilecek yolları anlatıyor olacağım. O halde ilk olarak sorunun ne sorduğunu anlayalım.

İlk Adım : Soruyu Anlamak

Soru bize kullanıcının fonksiyona bir sayı(int) dizisi girişi yapacağını söylüyor. Eğer bu dizinin elemanlarından herhangi birisi dizide iki defa veya iki defadan daha fazla kullanılmışsa fonksiyonun True döndürmesini bu şart geçerli değilse fonksiyonun False döndürmesini istiyor. Mesela [1,2,3,1] dizisi fonksiyona verildiği zaman 1 sayısından ikiden fazla kullanıldığı için fonksiyonumuz True döndürecektir. Fonksiyonumuza [1,2] girişi yapıldığı zaman ise False dönecektir çünkü herhangi bir sayı iki defa veya daha fazla kullanılmadı.

İkinci Adım : Sorunun Çözüm Yollarını Düşünmek

Tabii ki her sorunun birden fazla çözümü olabilir. İlk aklımıza gelen çözüm her zaman en iyisi olmayabilir ve soruyu direkt düşünmeden kodlamaya başladığımızda planlanmamış bir senaryoda her şey istediğimiz gibi gitmeyebilir. Bu yüzden öncelikle sorunun nasıl çözüleceğini düşünmemiz gerek. Öncelikle kafamızda şöyle bir senaryo oluşabilir : Listenin her sayısında teker durup listenin diğer sayılarıyla benziyor mu diye durduğumuz sayı dışındaki elemanları teker teker gezmek. Bunun için iç içe döngülerden yararlanmamız gerekir. Bu da bize oldukça performans kaybı yaşatacaktır. Bu sebeple daha optimum bir kod yazmaya çalışmalıyız. Bugün anlatacağım çözüm için pythonda bilmemiz gereken bir veri yapısı var : Set() hadi bu veri yapısının ne olduğuna detaylıca bakalım.

Set() Nedir,Ne İşe Yarar ?

Python’da set() bir veri yapısıdır ve tıpkı matematikteki kümeler gibi çalışır. Temel özellikleri şunlardır:

Tekil Elemanlar (Unique Elements): Bir set içinde tekrarlanan elemanlar bulunmaz. Aynı değeri birden fazla eklemeye çalışırsanız, set sadece bir tanesini saklar.
Sırasızdır (Unordered): Bir set içinde elemanların belirli bir sırası yoktur. Elemanlar, eklenme sırasına bağlı olmaksızın yer alır.
Değiştirilebilir (Mutable): Bir set içine yeni elemanlar ekleyebilir veya elemanları çıkarabilirsiniz. Ancak setin kendisi hashlenebilir olmalıdır, yani başka bir set’in içinde veya bir dictionary’nin anahtarı olarak kullanılamaz.
Hızlı Üyelik Testi (Fast Membership Test): set veri yapısı, elemanlarının var olup olmadığını hızlı bir şekilde kontrol edebilmenizi sağlar. Bunun nedeni, set’lerin hash tabanlı bir yapı kullanmasıdır.
Farklı Operasyonlar: set veri yapısıyla matematiksel küme operasyonları gerçekleştirebilirsiniz. Örneğin, iki set’in kesişimini (intersection), birleşimini (union) veya farkını (difference) alabilirsiniz.

Özetle, Python’da set veri yapısı, benzersiz elemanlardan oluşan sırasız ve değiştirilebilir bir koleksiyon sağlar. Özellikle veri temizliği, hızlı üyelik testleri ve kümeye dayalı matematiksel işlemler için kullanışlıdır.

Set() veri yapısının ne olduğunu öğrendiğimize göre bir sonraki cümleye geçmeden soruyu nasıl çözebileceğimizi bir daha düşünmek isteyebilirsiniz. Soruyu Çözüm Yolumuz : Aslında set() veri yapısını kullandığımız zaman soru oldukça basitleşiyor her eleman için iç içe döngüye gerek kalmıyor . Yapmamız gereken tek şey bir set() veri yapısı oluşturmak ve listenin içinde gezinmeye başlamak. Eğer listenin içinde gezdiğimiz eleman set() veri yapısının içinde yoksa ekliyoruz . Böylece eğer sıradaki elemanlardan birisi set() veri yapısının içine daha önce eklendiyse True Döndürüyoruz . Çözüm Yolumuzu algoritmamızı oluşturduğumuza göre kodlamaya başlayabiliriz.

Son Adım : Kod Yazma

					class Solution(object):
    def containsDuplicate(self, nums):
        seen = set()
        for num in nums:
            if num in seen:
                return True
            seen.add(num)
        return False
        				

Böylece sorumuzun algoritmasını oluşturup set() veri yapısını kullanarak soruyu çözdük. Tabii ki bu çözümden daha iyi performans gösteren veya daha yavaş çalışan birden fazla çözümü var. Aşağıda Başka bir çözüm yolunu anlatacağım.

Bonus Çözüm : Sorted() Metodu Kullanmak

					class Solution(object):
    def containsDuplicate(self, nums):
        sorted_nums = sorted(nums)
        for i in range(len(nums)-1):
            if(sorted_nums[i] == sorted_nums[i+1]):
                return True
        return False
        				

Bu çözümde öncelikle sorted() metodu ile listemizi sıralıyoruz. Böylece listede eğer iki tane aynı sayıdan varsa yan yana gelmiş oluyor. Örneğin [1,2,3,1] listesini sıraladığımızda [1,1,2,3] oluyor. Son yapacağımız işlem ise elemanların sonraki elemanla aynı olup olmadığını kontrol etmek . Aynı ise fonksiyonumuz True döndürüyor. Eğer aynı olan iki eleman bulunmadıysa False döndürüyoruz.