𝗟𝗲𝗲𝘁𝗰𝗼𝗱𝗲 𝟭𝟱𝟬 | 𝗗𝗮𝘆 𝟰: 𝗠𝗮𝗷𝗼𝗿𝗶𝘁𝘆 𝗘𝗹𝗲𝗺𝗲𝗻𝘁
Leetcode 169 meminta Anda untuk menemukan elemen mayoritas dalam sebuah array. Elemen mayoritas muncul lebih dari n / 2 kali. Kita berasumsi elemen tersebut selalu ada.
Anda dapat menyelesaikannya dengan dua cara.
Pendekatan 1: Metode Map
Metode ini menggunakan Map untuk menghitung berapa kali setiap angka muncul.
- Buat sebuah Map untuk menyimpan jumlah kemunculan.
- Iterasi melalui array.
- Perbarui jumlah untuk setiap angka.
- Iterasi melalui Map untuk menemukan angka dengan jumlah lebih besar dari n / 2.
Kompleksitas:
- Waktu: O(n) karena Anda menggunakan dua loop berurutan.
- Ruang: O(n) karena Map akan bertambah seiring dengan jumlah elemen unik.
Pendekatan 2: Algoritma Voting Boyer-Moore
Ini adalah cara yang dioptimalkan untuk menyelesaikan masalah tersebut menggunakan memori konstan.
Bayangkan angka-angka tersebut sebagai tim yang saling berlawanan. Setiap kali sebuah angka bertemu dengan angka yang berbeda, mereka akan saling meniadakan. Karena elemen mayoritas muncul lebih dari separuh waktu, ia akan selalu menjadi yang terakhir bertahan.
Cara kerjanya:
- Pilih sebuah kandidat dan atur jumlah (count) ke 0.
- Iterasi melalui array.
- Jika jumlahnya 0, tetapkan angka saat ini sebagai kandidat.
- Jika angka saat ini cocok dengan kandidat, tingkatkan jumlah sebesar 1.
- Jika tidak cocok, kurangi jumlah sebesar 1.
Kompleksitas:
- Waktu: O(n) karena Anda hanya melewati array satu kali.
- Ruang: O(1) karena Anda hanya menggunakan dua variabel.
Mengapa ini penting:
Kedua metode memiliki kompleksitas waktu O(n). Namun, pendekatan kedua menggunakan memori yang jauh lebih sedikit. Metode ini tidak memerlukan Map, sehingga lebih baik untuk dataset yang besar.
Sumber: https://dev.to/afuji/leetcode-150-day-4-majority-element-naive-vs-optimized-eo6