Majority Element

+10

Uzunluğu n olan bir tamsayı dizisi nums alırsın. İçindeki bir değer n / 2 kereden fazla görünür ve bu değere çoğunluk elemanı denir. Bu değeri döndür. Dizinin yarısından fazlasını oluşturan bir değer her zaman tektir, dolayısıyla tam olarak bir yanıt vardır.

Fonksiyon

majorityElement(nums: integer-array) → integer

numsinteger-array: tamsayı dizisinin yarısından fazlasını dolduran tek bir değer
Döndürürinteger: n / 2'den fazla kez görünen değer

Kısıtlar

1 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
Bir değer, nums.length / 2 sayısından daha fazla kez görünür.

Örnekler

Girdi: nums = [3, 9, 3, 3, 4]
Çıktı: 3
Açıklama: 3, be eleman içinde üç kez görünür. Üç, 5 / 2 = 2.5 değerinden büyüktür ve 9 ile 4 birer kez görünür.

Gönderirken +15 gizli test

Ek soru

Diziyi sıralamadan, O(n) zamanda ve O(1) ek bellek kullanarak çoğunluk elemanını bulabilir misin?

Çözüm

Her bir değerin kaç kez göründüğünü saymak soruyu yanıtlar, ancak bu sayımlar için bir hash map gerekir. Bunu bir kenara bırakmanın yolu, çoğunluk değerini özel kılan şeyi görmektir: Bu değer, diğer tüm değerlerin toplamından daha fazla kez bulunur. Her bir kopyasını farklı bir değerle eşleştirip ikisinin de üzerini çizin; geriye her zaman bazı kopyalar kalır. Boyer-Moore oylaması, bu eşleştirmeyi tek geçişte bir aday ve bir sayaç kullanarak yapar.

Bir karma haritasıyla sayma

Sezgi

Dizi üzerinde ilerle ve her değerden kaç kez gördüğünü tutan bir hash map kullan. Bir değerin sayacına bir ekledikten sonra, sayacın dizinin uzunluğunun yarısından büyük olup olmadığını kontrol et. Bu sınırı ilk aşan değer çoğunluktur; bu nedenle hemen döndürebilirsin.

[3, 9, 3, 3, 4] için 3'ün sayısı 0. indekste 1, 2. indekste 2 ve 3. indekste 3 olur. Beş elemandan üçünün aynı olması 2.5'ten fazladır; bu nedenle son elemanı okumadan 3'ü döndürürsün.

Hash map araması ve güncellemesi ortalama O(1) zaman alır; dolayısıyla zaman karmaşıklığı O(n)'dir. Map, yaklaşık n / 2 farklı değer tutabilir; bu nedenle ek bellek kullanımı O(n)'dir. Sonraki yaklaşım map'i ortadan kaldırır.

Algoritma

Değerden sayıya giden boş bir eşleme oluştur.
Her x öğesi için x sayacını 1 artır.
Bu sayacın 2 ile çarpımı dizinin uzunluğundan büyükse x değerini döndür.

def majorityElement(nums):
    counts = {}
    for x in nums:
        counts[x] = counts.get(x, 0) + 1
        if counts[x] * 2 > len(nums):
            return x

Boyer-Moore oylaması

Sezgi

Diziyi bir seçim yarışı olarak düşün. Bir candidate ve henüz hiçbir şeyin iptal etmediği oylarının count değerini tut. Adayla eşleşen bir öğe bir oy ekler. Farklı bir öğe bir oyu iptal eder ve ikisi birlikte yarıştan çekilir. Sayım 0 olduğunda sıradaki öğe yeni aday olur.

Sonda kalan değerin neden çoğunluk olduğunu açıklayalım: her iptal iki farklı değeri ortadan kaldırır, dolayısıyla çoğunluk değerinin en fazla bir kopyasını ortadan kaldırabilir. Çoğunluk değerin m kez göründüğünü varsayalım. Diğer öğelerin sayısı yalnızca n - m kadardır ve bu sayı m'den küçüktür; bu yüzden çoğunluk değerinin tüm kopyalarını iptal edemezler. Sonda hâlâ ayakta olan her oy son adaya aittir ve çoğunluk değerinin bir kopyası da bunların arasındadır; dolayısıyla aday çoğunluk değeridir.

[8, 8, 1, 1, 8, 1, 8] dizisinde sayım 1, 2, 1, 0 şeklinde ilerler: iki 1, iki 8'i iptal etmiştir. Sıradaki 8, sayımı 1'den başlatır; sonraki 1 onu iptal eder ve son 8 yeniden aday olur. 8 değerini döndürürsün. İki değişkenle tek geçiş, O(n) zaman ve O(1) bellek sağlar.

Algoritma

candidate'ı ilk elemana ve count'u 0'a ayarla.
Her x elemanı için, count 0 ise x'i aday yap.
x adayla eşitse count'u 1 artır. Aksi takdirde 1 azalt.
Son elemandan sonra candidate'ı döndür.

def majorityElement(nums):
    candidate = nums[0]
    count = 0
    for x in nums:
        if count == 0:
            candidate = x  # the old candidate's votes are used up
        if x == candidate:
            count += 1
        else:
            count -= 1  # x and one copy of the candidate cancel out
    return candidate

Tuzaklar ve uç durumlar

Yanlış yanıtların çoğu orta çizgiden ya da sayaçtan gereğinden fazla anlam çıkarmaktan kaynaklanır.

“Yarısından fazla” katı bir koşuldur. count >= n / 2, 4 öğeden 2’sini kabul eder; bu çoğunluk değildir. count * 2 > n karşılaştırmasını kullanırsan yuvarlama araya giremez.
Boyer-Moore’da son count değeri, çoğunluğun kaç kez göründüğü anlamına gelmez. [8, 8, 1, 1, 8, 1, 8] için sonuç 1 olurken, 8 dört kez görünür.
candidate = nums[0] ve count = 1 ile başlamak yalnızca döngü 1. indeksten başlıyorsa işe yarar. Döngüyü 0. indeksten başlatırsan ilk öğe iki kez oy verir: [1, 2, 2] için sayaç 0 olur ve 1 döndürülür.
Boyer-Moore, çoğunluğun var olduğu garantisine dayanır. Çoğunluk içermeyen [1, 2, 3] dizisinde bile 3 döndürür. Girdide çoğunluk olmayabilirse, adaya güvenmeden önce ikinci bir geçişte onu say.

Sıkça sorulan sorular4

Boyer-Moore oylama algoritması nedir?

Bir listenin yarısından fazlasında bulunan değeri, O(1) bellek kullanarak tek geçişte bulur. Bir aday ve sayaç tutar: eşleşen bir öğe sayacı bir artırır, farklı bir öğe bir azaltır ve sayaç 0 olduğunda sonraki öğe aday olur. Çoğunluk değeri, diğer tüm değerlerin toplamından fazla olduğundan, sonunda geriye kalan aday odur.

Majority Element için zaman ve uzay karmaşıklığı nedir?

Boyer-Moore oylama algoritması O(n) zaman ve O(1) ek alan kullanır. Bir hash map ile sayma da O(n) zaman alır, ancak sayımlar için O(n) alan gerektirir. Önce sıralama yapmak O(n log n) zaman alır.

Çoğunluk Elemanı sıralama kullanılarak çözülebilir mi?

Evet. Sıraladıktan sonra çoğunluk elemanının tüm kopyaları dizinin yarısından uzun tek bir blokta yer alır ve böyle bir blok orta konumu kapsar. Bu yüzden n / 2 indeksindeki, aşağı yuvarlanmış eleman cevaptır. Yazması kısa olsa da O(n log n) zaman alır.

Ya dizide çoğunluk elemanı yoksa?

Boyer-Moore, dizinin yarısından fazlasını hiçbir değer doldurmasa bile her zaman bir aday döndürür. Adayı sayan ikinci bir geçiş ekle ve yalnızca sayısı n / 2 değerinden fazlaysa kabul et. Toplam karmaşıklık O(n) zaman ve O(1) alan olarak kalır.

Python

def majorityElement(nums):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Girdi

nums = [3, 9, 3, 3, 4]

Beklenen