LeetCode 380: O(1) Zaman Karmaşıklığında Ekle, Sil ve Rastgele Eleman Getirme

LeetCode 380: O(1) Zaman Karmaşıklığında Ekle, Sil ve Rastgele Eleman Getirme

LeetCode’un 380. sorusu, “Insert Delete GetRandom O(1)” adlı oldukça zorlayıcı bir problem sunuyor. Bu problemde, eleman ekleme, silme ve rastgele bir eleman getirme işlemlerinin hepsinin ortalama O(1) zaman karmaşıklığında gerçekleşmesini sağlayan bir veri yapısı oluşturmamız gerekiyor. Başlangıçta bu oldukça imkansız gibi görünse de, doğru veri yapısı ve strateji ile bu başarılabilir.

Bu makalede, JavaScript kullanarak bu sorunu nasıl çözdüğümü adım adım açıklayacağım. Amacımız, herhangi bir elemanı sabit sürede eklemek, silmek ve rastgele bir eleman almak.

Çözümün Temeli: HashMap ve Array

Bu problemin çözümü, iki veri yapısının birlikte kullanılmasına dayanır: Bir HashMap (JavaScript’te Map) ve bir Array. HashMap, elemanları indekslerine eşlemede kullanılırken, Array ise elemanların sıralı bir şekilde tutulmasını sağlar. İşte bu ikili, O(1) karmaşıklığını elde etmemizi mümkün kılıyor.

Öncelikle, HashMap’imizde her bir elemanı, array içindeki indeksine eşleştiriyoruz. Bu sayede, bir elemanı silmek istediğimizde, önce HashMap’ten indeksini buluyor ve sonra Array’deki o indeksi siliyoruz. Ayrıca, rastgele bir eleman getirmek istediğimizde, Array’in uzunluğundan rastgele bir indeks üretiyor ve bu indeksteki elemanı alıyoruz. Bu işlemler, her ikisi de O(1) zaman karmaşıklığında gerçekleştiriliyor.

JavaScript Kodu

class RandomizedSet {
    constructor() {
        this.map = new Map(); // Eleman-indeks eşleştirmesi için
        this.array = []; // Elemanları saklamak için
    }

    insert(val) {
        if (this.map.has(val)) return false;
        this.map.set(val, this.array.length);
        this.array.push(val);
        return true;
    }

    remove(val) {
        if (!this.map.has(val)) return false;
        let index = this.map.get(val);
        let last = this.array.pop(); // Son elemanı al

        if (last !== val) { // Silinen eleman son eleman değilse
            this.array[index] = last; // Son elemanı silinenin yerine koy
            this.map.set(last, index); // Son elemanın indeksini güncelle
        }
        this.map.delete(val);
        return true;
    }

    getRandom() {
        return this.array[Math.floor(Math.random() * this.array.length)];
    }
}

Yukarıdaki kodda, insert fonksiyonu yeni bir eleman ekler, remove fonksiyonu bir elemanı siler ve getRandom fonksiyonu rastgele bir eleman döndürür. Tüm fonksiyonlar, ortalama O(1) zaman karmaşıklığında çalışır.

Optimizasyonlar ve Detaylar

Kodda, silme işlemi sırasında son elemanın silinen elemanın yerine konması önemli bir optimizasyondur. Bu, array’in yeniden indekslenmesini önler ve O(1) karmaşıklığını korur. Ayrıca, HashMap’in kullanımı, elemanların hızlı bir şekilde bulunmasını sağlar.

Bu çözüm, hem zaman hem de alan karmaşıklığı açısından oldukça verimlidir. Ancak, hash fonksiyonunun performansı, pratik uygulamalarda zaman karmaşıklığını etkileyebilir. Bu nedenle, iyi bir hash fonksiyonunun seçilmesi önemlidir.

Sonuç

LeetCode’un 380. sorusu, veri yapıları ve algoritmalar konusunda derin bir anlayış gerektiren zorlu bir problemdir. Bu makalede, JavaScript kullanarak O(1) zaman karmaşıklığını sağlayan bir çözüm sunduk. Umarım bu açıklama, sorunu anlamanıza ve çözmenize yardımcı olmuştur. Daha fazla algoritma ve veri yapısı örneği için fatihsoysal.com sitesini ziyaret edebilirsiniz.

Faydalı bulabileceğiniz bir diğer kaynak ise: Dev.to makalesi

#Etiketler

#LeetCode #JavaScript #Algoritma #VeriYapısı #O(1) #getRandom #insert #delete #HashMap #Map #Array #RandomizedSet #Programlama