Majority Element

Q: Dizide çoğunluk elemanı olmayabilirse ne olur?

Boyer-Moore her zaman bir aday döndürür: [1, 2, 3] için 3 döndürür. Adayı sayan ikinci bir geçiş ekleyin ve yalnızca sayısı n / 2 değerinden fazlaysa kabul edin. Toplam süre O(n), alan kullanımı ise O(1) olarak kalır.

KolayHashing

+10

Uzunluğu n olan bir tamsayı dizisi nums alırsın. Dizide 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ı kaplayan bir değer her zaman tektir, dolayısıyla tam olarak bir yanıt vardır.

Fonksiyon

majorityElement(nums: integer-array) → integer

numsinteger-array: Bir değerin dizinin yarısından fazlasında yer aldığı tamsayı dizisi
Döndürürinteger: n / 2 kereden fazla görünen değer

Kısıtlar

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

Örnekler

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

Ek soru

O(n) zamanda ve O(1) ek bellek kullanarak, n / 3'ten daha fazla kez görünen her değeri bulabilir misin?

Çözüm

Çoğunluk, bir araya getirilen diğer tüm değerlerden daha fazladır. Farklı değer çiftlerinin üzerini çizin; çoğunluk değerinin bazı kopyaları her zaman hayatta kalır. Boyer-Moore oylaması bu eşleştirmeyi tek bir geçişte, bir aday ve bir sayaçla yapar; böylece sayımlar için bir karma eşlemesine ihtiyaç duymazsınız.

Bir hash map ile say

Sezgi

Bir karma haritada her değerin sayısını tut ve sayısı uzunluğun yarısını aşan ilk değeri döndür. [3, 9, 3, 3, 4] için 3'ün sayısı 3. indekste 3'e ulaşır; bu, 2.5'ten fazla olduğu için 4'ü okumadan döndürürsün.

Her arama ortalama O(1) olduğundan süre O(n)'dir, ancak harita yaklaşık n / 2 farklı değer tutabilir: O(n) bellek.

Algoritma

Değerden sayıya bir boş eşleme oluşturun.
Her x öğesi için x sayacına 1 ekleyin.
Bu sayının 2 katı dizinin uzunluğundan büyükse x değerini döndürün.

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 oylama algoritması

Sezgi

Bir candidate ve henüz iptal edilmemiş 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 de yarıştan çıkar. Sayı 0 olduğunda, sonraki öğe aday olur.

Her iptal iki farklı değeri ortadan kaldırır, dolayısıyla çoğunluk değerinden en fazla bir kopya eksilir. Çoğunluk değeri m kez görünüyorsa, diğer n - m öğenin sayısı m'den azdır ve çoğunluk değerinin tüm kopyalarını iptal edemez. Sonda ayakta kalan her oy son adaya aittir ve bunların arasında çoğunluk değerinin bir kopyası da vardır.

[8, 8, 1, 1, 8, 1, 8] dizisinde, 1'ler her iki 8'i de iptal ederken sayı 1, 2, 1, 0 olur. Sonraki 8 sayacı 1'den yeniden başlatır, sonraki 1 onu iptal eder ve son 8 yeniden aday olur. İki değişkenle tek geçiş, O(n) zaman ve O(1) bellek gerektirir.

Algoritma

candidate'ı ilk öğe ve count'u 0 olarak ayarla.
Her x öğesi için, count 0 ise x'i aday yap.
x adayla eşitse, count'u 1 artır. Aksi takdirde 1 azalt.
Son öğeden 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

“Yarısından fazla” kesin bir koşuldur. count >= n / 2 ifadesi, 4 kopyadan 2 tanesini kabul eder; bu çoğunluk değildir. count * 2 > n ile karşılaştırın; böylece yuvarlama da sorun yaratmaz.
Son count değerini çoğunluğun frekansı olarak okumak. [8, 8, 1, 1, 8, 1, 8] için değer 1 olurken, 8 dört kez görünür.
candidate = nums[0] ve count = 1 ile başlayıp sonra 0 indeksinden döngüye girmek. İlk eleman iki kez oy verir: [1, 2, 2] için sayım 0 olur ve 1 döndürülür.

Sıkça sorulan sorular3

Çoğunluk Elemanı'nın zaman ve alan karmaşıklığı nedir?

Boyer-Moore oylaması O(n) zamanda çalışır ve O(1) ek alan kullanır. Bir karma haritayla 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ıralamadan 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 nedenle, n / 2 aşağı yuvarlanmış değerindeki dizin öğesi yanıttır; zaman maliyeti O(n log n)'dir.

Dizide çoğunluk elemanı olmayabilirse ne olur?

Boyer-Moore her zaman bir aday döndürür: [1, 2, 3] için 3 döndürür. Adayı sayan ikinci bir geçiş ekleyin ve yalnızca sayısı n / 2 değerinden fazlaysa kabul edin. Toplam süre O(n), alan kullanımı ise O(1) olarak kalır.

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

Test #1

Test #2

Argüman

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

Beklenen Çıktı