Majority Element

Q: Bagaimana jika array mungkin tidak memiliki elemen mayoritas?

Boyer-Moore selalu mengembalikan suatu kandidat: pada [1, 2, 3] , algoritma ini mengembalikan 3. Tambahkan tahap kedua untuk menghitung kandidat tersebut dan menerimanya hanya jika jumlahnya lebih dari n / 2 . Totalnya tetap membutuhkan waktu O(n) dan ruang O(1).

MudahHashing

+10

Kamu mendapatkan array bilangan bulat nums dengan panjang n. Salah satu nilai muncul di dalamnya lebih dari n / 2 kali, dan nilai itu disebut elemen mayoritas. Kembalikan nilai tersebut. Nilai yang mengisi lebih dari setengah array selalu unik, jadi hanya ada satu jawaban.

Fungsi

majorityElement(nums: integer-array) → integer

numsinteger-array: array bilangan bulat, dengan satu nilai mengisi lebih dari setengah bagiannya
Mengembalikaninteger: nilai yang muncul lebih dari n / 2 kali

Batasan

1 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
Satu nilai muncul lebih dari nums.length / 2 kali.

Contoh

Input: nums = [3, 9, 3, 3, 4]
Output: 3
Penjelasan: 3 muncul tiga kali dalam lima elemen. Tiga lebih besar dari 5 / 2 = 2.5, dan 9 serta 4 masing-masing muncul satu kali.

Pertanyaan lanjutan

Bisakah kamu menemukan setiap nilai yang muncul lebih dari n / 3 kali, dalam waktu O(n) dengan memori tambahan O(1)?

Solusi

Jumlah kemunculan mayoritas lebih banyak daripada gabungan semua nilai lainnya. Coret pasangan nilai yang berbeda, dan sebagian salinannya akan selalu tersisa. Pemungutan suara Boyer-Moore memasangkan nilai-nilai tersebut dalam satu kali lintasan dengan satu kandidat dan satu penghitung, jadi kamu tidak memerlukan hash map untuk menghitung jumlahnya.

Hitung dengan hash map

Intuisi

Hitung setiap nilai dalam hash map dan kembalikan nilai pertama yang jumlah kemunculannya melebihi setengah panjangnya. Untuk [3, 9, 3, 3, 4], jumlah kemunculan 3 mencapai 3 pada indeks 3, lebih dari 2.5, jadi kamu mengembalikan nilai tersebut sebelum membaca 4.

Setiap pencarian rata-rata membutuhkan O(1), jadi waktunya O(n), tetapi map dapat menyimpan sekitar n / 2 nilai yang berbeda: memori O(n).

Algoritma

Buat map kosong dari nilai ke jumlah.
Untuk setiap elemen x, tambahkan 1 ke jumlah x.
Jika jumlah itu dikalikan 2 lebih besar daripada panjang array, kembalikan x.

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

Pemungutan suara Boyer-Moore

Intuisi

Simpan candidate dan count untuk jumlah suaranya yang belum dibatalkan. Elemen yang sama dengan kandidat menambah satu suara. Elemen yang berbeda membatalkan satu suara, dan keduanya keluar dari persaingan. Saat jumlahnya 0, elemen berikutnya menjadi kandidat.

Setiap pembatalan menghapus dua nilai yang berbeda, jadi paling banyak satu salinan mayoritas. Jika mayoritas muncul m kali, jumlah elemen lainnya, n - m, lebih sedikit dari m dan tidak bisa membatalkan semua salinannya. Semua suara yang tersisa pada akhir proses dimiliki kandidat terakhir, dan salah satunya adalah salinan mayoritas.

Pada [8, 8, 1, 1, 8, 1, 8], jumlahnya menjadi 1, 2, 1, 0 saat angka 1 membatalkan kedua angka 8. Angka 8 berikutnya memulai lagi dari 1, angka 1 berikutnya membatalkannya, lalu angka 8 terakhir menjadi kandidat lagi. Satu kali penelusuran dengan dua variabel membutuhkan waktu O(n) dan memori O(1).

Algoritma

Tetapkan candidate sebagai elemen pertama dan count menjadi 0.
Untuk setiap elemen x, jika count bernilai 0, jadikan x sebagai kandidat.
Jika x sama dengan kandidat, tambahkan 1 ke count. Jika tidak, kurangi 1.
Setelah elemen terakhir, kembalikan candidate.

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

Jebakan dan kasus tepi

"Lebih dari setengah" berarti harus benar-benar lebih besar. count >= n / 2 menerima 2 salinan dari 4, padahal itu bukan mayoritas. Bandingkan dengan count * 2 > n, sehingga pembulatan tidak menjadi masalah.
Menganggap count terakhir sebagai frekuensi mayoritas. Untuk [8, 8, 1, 1, 8, 1, 8], nilainya berakhir di 1, sedangkan 8 muncul empat kali.
Memulai dengan candidate = nums[0] dan count = 1, lalu melakukan perulangan mulai dari indeks 0. Elemen pertama memberikan suara dua kali: pada [1, 2, 2], nilai count berakhir di 0 dan kamu mengembalikan 1.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu dan ruang dari Majority Element?

Voting Boyer-Moore berjalan dalam waktu O(n) dan menggunakan ruang tambahan O(1). Menghitung dengan hash map juga membutuhkan waktu O(n), tetapi memerlukan ruang O(n) untuk menyimpan hitungan. Mengurutkan terlebih dahulu membutuhkan waktu O(n log n).

Bisakah Majority Element diselesaikan dengan mengurutkan?

Ya. Setelah diurutkan, semua salinan elemen mayoritas berada dalam satu blok yang panjangnya lebih dari setengah array, dan blok semacam itu mencakup posisi tengah. Jadi, elemen pada indeks n / 2, dibulatkan ke bawah, adalah jawabannya, dengan kompleksitas waktu O(n log n).

Bagaimana jika array mungkin tidak memiliki elemen mayoritas?

Boyer-Moore selalu mengembalikan suatu kandidat: pada [1, 2, 3], algoritma ini mengembalikan 3. Tambahkan tahap kedua untuk menghitung kandidat tersebut dan menerimanya hanya jika jumlahnya lebih dari n / 2. Totalnya tetap membutuhkan waktu O(n) dan ruang O(1).

def majorityElement(nums):
    # Tulis kodemu di sini

Tes #1

Tes #2

Argumen

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

Output yang diharapkan