𝗟𝗲𝗲𝘁𝗰𝗼𝗱𝗲 𝟭𝟱𝟬 | 𝗗𝗮𝘆 𝟰: 𝗠𝗮𝗷𝗼𝗿𝗶𝘁𝘆 𝗘𝗹𝗲𝗺𝗲𝗻𝘁
Leetcode 169 meminta anda mencari elemen majoriti dalam satu tatasusunan. Elemen majoriti muncul lebih daripada n / 2 kali. Kita mengandaikan ia sentiasa wujud.
Anda boleh menyelesaikannya dengan dua cara.
Pendekatan 1: Kaedah Map
Kaedah ini menggunakan Map untuk mengira berapa kali setiap nombor muncul.
- Cipta satu Map untuk menyimpan bilangan.
- Gelung melalui tatasusunan tersebut.
- Kemas kini bilangan bagi setiap nombor.
- Gelung melalui Map untuk mencari nombor dengan bilangan yang lebih tinggi daripada n / 2.
Kompleksiti:
- Masa: O(n) kerana anda menggunakan dua gelung berturutan.
- Ruang: O(n) kerana saiz Map bertambah mengikut bilangan elemen unik.
Pendekatan 2: Algoritma Pengundian Boyer-Moore
Ini adalah cara yang dioptimumkan untuk menyelesaikan masalah ini menggunakan memori malar.
Bayangkan nombor-nombor tersebut sebagai pasukan yang bertentangan. Setiap kali satu nombor bertemu dengan nombor yang berbeza, mereka akan saling membatalkan satu sama lain. Memandangkan elemen majoriti muncul lebih daripada separuh masa, ia akan sentiasa menjadi yang terakhir bertahan.
Cara ia berfungsi:
- Pilih satu calon dan tetapkan bilangan kepada 0.
- Gelung melalui tatasusunan tersebut.
- Jika bilangan adalah 0, tetapkan nombor semasa sebagai calon.
- Jika nombor semasa sepadan dengan calon, tambahkan bilangan sebanyak 1.
- Jika tidak sepadan, kurangkan bilangan sebanyak 1.
Kompleksiti:
- Masa: O(n) kerana anda hanya melalui tatasusunan tersebut sekali sahaja.
- Ruang: O(1) kerana anda hanya menggunakan dua pemboleh ubah.
Mengapa ia penting:
Kedua-dua kaedah mempunyai kompleksiti masa O(n). Walau bagaimanapun, pendekatan kedua menggunakan memori yang jauh lebih sedikit. Ia tidak memerlukan Map. Ini menjadikannya lebih baik untuk set data yang besar.
Sumber: https://dev.to/afuji/leetcode-150-day-4-majority-element-naive-vs-optimized-eo6