Dizideki Çoğunluk Öğeyi Bulmanın 2 Yolu: Basit ve Optimize

Veri yapıları ve algoritmaların derinliklerine dalarken, çoğu programcının karşılaştığı temel bir sorunla karşılaşırsınız: Bir dizideki çoğunluk öğeyi nasıl bulursunuz? LeetCode 169 problemi, bu sorunu çözmeyi gerektirir ve çoğunluk öğenin dizide n/2 defadan daha fazla göründüğünü varsaymanız gerekir.

Bu makalede, problemi çözmek için iki farklı yaklaşımı inceleyeceğiz: Naif bir yöntem olan Frekans Haritası ve optimize edilmiş bir algoritma olan Boyer-Moore Çoğunluk Oylama Algoritması. Her iki yöntemin de avantajlarını ve dezavantajlarını karşılaştırarak, hangi durumlarda hangisini kullanmanız gerektiğini öğreneceksiniz.

Frekans Haritasıyla Naif Çözüm

Frekans haritası yaklaşımı, dizideki her bir öğenin kaç kez tekrarlandığını saymak için bir harita veri yapısından yararlanır. Bu yöntem, özellikle küçük veri kümeleri için anlaşılması kolay ve uygulanması basit bir çözüm sunar.

Başlangıç olarak, aşağıdaki diziyi kullanacağız:

nums = [2, 4, 2, 2, 4, 4, 4]

Bu dizideki çoğunluk öğeyi bulmak için ilk adım, bir counts haritası oluşturmaktır:

const counts = new Map();

Ardından, diziyi tarayarak her bir öğenin frekansını hesaplarız:

for (const num of nums) {
  counts.set(num, (counts.get(num) ?? 0) + 1);
}

Bu döngüde, her bir num için haritada bir giriş oluşturulur. Eğer num daha önce görülmemişse, counts.get(num) undefined döndürür ve nullish coalescing operatörü (??) sayesinde varsayılan değer olarak 0 kullanılır. Böylece, frekans sayacı 1 olarak başlatılır. Eğer num daha önce görülmüşse, mevcut frekans değeri alınır ve 1 artırılır.

Son olarak, haritadaki her bir girişteki frekans değeri, dizinin uzunluğunun yarısından büyük olup olmadığına bakılır:

for (const [num, count] of counts) {
  if (count > nums.length / 2) {
    return num;
  }
}

Verilen dizide, counts haritası şu şekilde oluşur:

counts = [[2, 3], [4, 4]]

Burada, 4 öğesi dizide 4 kez görülmüş olup, dizinin uzunluğunun yarısından (7/2 = 3.5) daha fazladır. Bu nedenle, 4 çoğunluk öğesi olarak tanımlanır.

• Zaman karmaşıklığı: O(n) — Diziyi iki kez tarar, ancak her tarama doğrusal zamanda gerçekleşir.
• Alan karmaşıklığı: O(n) — Harita, dizideki benzersiz öğe sayısı kadar yer kaplar.

Boyer-Moore Çoğunluk Oylama Algoritmasıyla Optimize Çözüm

1981 yılında Robert S. Boyer ve J Strother Moore tarafından geliştirilen Boyer-Moore algoritması, çoğunluk öğeyi bulmak için doğrusal zamanda çalışan ve sabit bellek kullanımı sağlayan bir yöntemdir. Bu algoritma, özellikle büyük veri kümeleri için idealdir.

Algoritmanın temel mantığı, bir aday ve bir sayac kullanmaktır. Diziyi tararken, her bir öğe için sayacı güncelleriz. Eğer sayaç sıfırsa, mevcut öğeyi yeni aday olarak belirleriz. Eğer öğe adaya eşitse, sayacı artırırız; aksi takdirde, sayacı azaltırız.

Aşağıdaki kodda, bu algoritmanın nasıl uygulandığını görebilirsiniz:

function majorityElement(nums) {
  let candidate = null;
  let count = 0;
  
  for (const num of nums) {
    if (count === 0) {
      candidate = num;
    }
    count += num === candidate ? 1 : -1;
  }
  
  return candidate;
}

Bu algoritmayı, önceki dizimize uygulayarak adım adım inceleyelim:

| Öğe | Sayac Sıfır mı? | Aday | Sayac | |------|-----------------|-------|-------| | 2 | Evet | 2 | 1 | | 4 | Hayır | 2 | 0 | | 2 | Evet | 2 | 1 | | 2 | Hayır | 2 | 2 | | 4 | Hayır | 2 | 1 | | 4 | Hayır | 2 | 0 | | 4 | Evet | 4 | 1 |

Sonuç olarak, algoritma 4 değerini çoğunluk öğesi olarak doğru bir şekilde tanımlar.

• Zaman karmaşıklığı: O(n) — Diziyi sadece bir kez tarar.
• Alan karmaşıklığı: O(1) — Sadece iki değişken kullanır ve ek bellek gerektirmez.

Hangisini Seçmeli?

Her iki yaklaşım da doğrusal zamanda çalışırken, Frekans Haritası yöntemi daha fazla bellek kullanır. Bu nedenle, Bellek kullanımının kritik olduğu durumlarda Boyer-Moore algoritması tercih edilmelidir. Ancak, Frekans Haritası yöntemi daha anlaşılır ve debug edilmesi kolaydır.

Eğer problemi basit ve anlaşılır bir şekilde çözmek istiyorsanız Frekans Haritası ideal bir seçimdir. Ancak, performans ve ölçeklenebilirlik önem taşıyorsa, Boyer-Moore algoritması daha verimli bir çözüm sunar. Gelecekteki projelerinizde bu algoritmaları doğru bağlamda kullanarak hem zaman hem de bellek tasarrufu sağlayabilirsiniz.