LeetCode Top Interview 150-169: Çoğunluk Elemanı
Merhaba, bugün LeetCode’un Top Interview 150-169 serisindeki “Çoğunluk Elemanı” problemini ele alacağız. Bu problem, bir dizide en çok görünen elemanı bulmayı hedefler. Bir dizi içinde, bu eleman toplam eleman sayısının yarısından fazlasını temsil eder.
Problemin Tanımı
Bir dizi nums veriliyor. Bu dizide en çok görünen elemanı bulun. Bu elemanın dizi içinde toplam eleman sayısının yarısından fazlasını temsil ettiğini varsayıyoruz.
Örneğin:
Giriş: nums = [2,2,1,1,1,2,2] Çıkış: 2
Bu durumda 2 sayısı toplam eleman sayısının (7) yarısından fazla (4) görünmektedir.
Çözümler
Bu problemi çözmek için birkaç farklı yöntem kullanabiliriz.
1. Hash Tablosu
En basit çözümlerden biri hash tablosu kullanmaktır. Hash tablosunda her elemanın kaç kez göründüğünü sayabiliriz. Daha sonra, en yüksek sayıya sahip elemanı döndürürüz.
“`python
def majorityElement(nums):
counts = {}
for num in nums:
if num in counts:
counts[num] += 1
else:
counts[num] = 1
return max(counts, key=counts.get)
nums = [2,2,1,1,1,2,2]
print(majorityElement(nums)) # Çıkış: 2
“`
2. Sıralama
Bir diğer yaklaşım ise diziyi sıralamaktır. Sıralı bir dizide, çoğunluk elemanı ortasında yer alacaktır. Dolayısıyla diziyi sıraladıktan sonra orta elemanı döndürebiliriz.
“`python
def majorityElement(nums):
nums.sort()
return nums[len(nums) // 2]
nums = [2,2,1,1,1,2,2]
print(majorityElement(nums)) # Çıkış: 2
“`
3. Boyer-Moore Voting Algorithm
Boyer-Moore Voting Algorithm, bu problemi en etkili şekilde çözen bir algoritmadır. Bu algoritma, iki değişken kullanır: candidate ve count. candidate, şu anki çoğunluk adayını temsil ederken, count, bu adayın kaç kez göründüğünü sayar. Her elemanı dolaşırken, eğer count 0 ise candidate‘ı mevcut elemana ayarlarız. Eğer mevcut eleman candidate ile aynıysa count‘u arttırır, değilse count‘u azaltırız. Son olarak candidate‘ı döndürürüz.
“`python
def majorityElement(nums):
candidate = None
count = 0
for num in nums:
if count == 0:
candidate = num
count += 1 if num == candidate else -1
return candidate
nums = [2,2,1,1,1,2,2]
print(majorityElement(nums)) # Çıkış: 2
“`
Karmaşıklık Analizi
Yukarıdaki çözümlerin karmaşıklıklarını inceleyelim:
| Yöntem | Zaman Karmaşıklığı | Uzay Karmaşıklığı |
|—|—|—|
| Hash Tablosu | O(n) | O(n) |
| Sıralama | O(n log n) | O(1) |
| Boyer-Moore Voting Algorithm | O(n) | O(1) |
Boyer-Moore Voting Algorithm, zaman ve uzay açısından en verimli çözümdür.
Sonuç
Bu makalede, LeetCode’un Top Interview 150-169 serisinden “Çoğunluk Elemanı” problemini inceledik. Farklı çözümlerden bahsettik ve bunların karmaşıklıklarını analiz ettik. Boyer-Moore Voting Algorithm, bu problemi en etkili şekilde çözen yöntemdir.
Daha fazla bilgi için aşağıdaki kaynakları inceleyebilirsiniz:
#Etiketler
#LeetCode #TopInterview #MajorityElement #Algoritma #VeriYapıları #Programlama #Python #BoyerMooreVotingAlgorithm