Leetcode 150 | Gün 4: Çoğunluk Elemanı
Leetcode 169, bir dizideki çoğunluk elemanını bulmanızı ister. Çoğunluk elemanı, n / 2'den fazla kez görünür. Her zaman var olduğunu varsayıyoruz.
Bunu iki şekilde çözebilirsiniz.
Yaklaşım 1: Map Yöntemi
Bu yöntem, her sayının kaç kez göründüğünü saymak için bir Map kullanır.
- Sayımları saklamak için bir Map oluşturun.
- Dizi üzerinde döngü kurun.
- Her sayı için sayımı güncelleyin.
- Sayımı n / 2'den yüksek olan sayıyı bulmak için Map üzerinde döngü kurun.
Karmaşıklık:
- Zaman: O(n), çünkü iki ardışık döngü kullanıyorsunuz.
- Alan: O(n), çünkü Map, benzersiz eleman sayısıyla birlikte büyür.
Yaklaşım 2: Boyer-Moore Oylama Algoritması
Bu, sabit bellek kullanarak problemi çözmenin optimize edilmiş bir yoludur.
Sayıları rakip takımlar gibi düşünün. Bir sayı farklı bir sayıyla karşılaştığında, birbirlerini nötrlerler. Çoğunluk elemanı vaktin yarısından fazlasında göründüğü için, her zaman ayakta kalan son eleman olacaktır.
Nasıl çalışır:
- Bir aday seçin ve sayımı 0 olarak ayarlayın.
- Dizi üzerinde döngü kurun.
- Eğer sayı 0 ise, mevcut sayıyı aday olarak belirleyin.
- Eğer mevcut sayı aday ile eşleşiyorsa, sayımı 1 artırın.
- Eğer eşleşmiyorsa, sayımı 1 azaltın.
Karmaşıklık:
- Zaman: O(n), çünkü dizinin üzerinden yalnızca bir kez geçiyorsunuz.
- Alan: O(1), çünkü yalnızca iki değişken kullanıyorsunuz.
Neden önemli:
Her iki yöntemin de zaman karmaşıklığı O(n)'dir. Ancak, ikinci yaklaşım çok daha az bellek kullanır. Bir Map'e ihtiyaç duymaz. Bu da onu büyük veri kümeleri için daha iyi kılar.
Kaynak: https://dev.to/afuji/leetcode-150-day-4-majority-element-naive-vs-optimized-eo6