𝗟𝗲𝗲𝘁𝗰𝗼𝗱𝗲 𝟭𝟱𝟬 | 𝗗𝗮𝘆 𝟰: 𝗠𝗮𝗷𝗼𝗿𝗶𝘁𝘆 𝗘𝗹𝗲𝗺𝗲𝗻𝘁
Leetcode 169 inakuomba utafute elementu ya wingi (majority element) kwenye array. Elementu ya wingi hutokea zaidi ya n / 2 mara. Tunachukulia kwamba kila wakati ipo.
Unaweza kutatua hili kwa njia mbili.
Njia ya 1: Njia ya Map
Njia hii hutumia Map kuhesabu ni mara ngapi kila namba inatokea.
- Tengeneza Map ya kuhifadhi idadi ya hesabu.
- Pitisha loop kwenye array.
- Sasisha idadi ya kila namba.
- Pitisha loop kwenye Map ili kupata namba yenye idadi kubwa kuliko n / 2.
Ugumu (Complexity):
- Muda: O(n) kwa sababu unatumia loop mbili zinazofuatana.
- Nafasi: O(n) kwa sababu Map hukua kulingana na idadi ya elementu za kipekee.
Njia ya 2: Algorithm ya Boyer-Moore Voting
Hii ni njia iliyoboreshwa ya kutatua tatizo hili kwa kutumia kumbukumbu ya kudumu (constant memory).
Fikiria namba hizo kama timu zinazopingana. Kila mara namba inapokutana na namba tofauti, zinabatilisha nyingine. Kwa kuwa elementu ya wingi hutokea zaidi ya nusu ya muda, itakuwa ndiyo itakayobaki mwisho.
Jinsi inavyofanya kazi:
- Chagua mgombea (candidate) na uweke idadi (count) kuwa 0.
- Pitisha loop kwenye array.
- Ikiwa idadi ni 0, weka namba ya sasa kuwa mgombea.
- Ikiwa namba ya sasa inafanana na mgombea, ongeza idadi kwa 1.
- Ikiwa haifanani, punguza idadi kwa 1.
Ugumu (Complexity):
- Muda: O(n) kwa sababu unapita kwenye array mara moja tu.
- Nafasi: O(1) kwa sababu unatumia variable mbili tu.
Kwa nini ni muhimu:
Njia zote mbili zina ugumu wa muda (time complexity) wa O(n). Hata hivyo, njia ya pili hutumia kumbukumbu kidogo zaidi. Haidai Map. Hii inafanya iwe bora zaidi kwa seti kubwa za data.
Chanzo: https://dev.to/afuji/leetcode-150-day-4-majority-element-naive-vs-optimized-eo6