Ky postim është pjesë e serisë ku unë do të zbërthej problemet e kodimit që kam zgjidhur dhe do të ndaj mësimet që kam mësuar duke gjetur një përgjigje. Gjuha e kodimit do të jetë në JavaScript.
Mirë se vini në një vështrim tjetër në rrëmujën e mendjes sime duke shpjeguar proceset që përdor për zgjidhjen e sfidave të kodimit! Kjo sfidë nuk është shumë intensive. Meqenëse Elementi i shumicës është i shkurtër në përshkrimin e tij, kështu që unë do të jem i shkurtër në shpjegimet e mia që vijojnë.
Këtë sfidë mund ta gjeni “këtu”.
Kuptimi i problemit
E përshkruar thjesht, këtu është citati direkt nga sfida:
“Duke pasur parasysh një grup me madhësi n, gjeni elementin e shumicës. Elementi i shumicës është elementi që shfaqet më shumë se
⌊ n/2 ⌋
herë.
Ju mund të supozoni se grupi nuk është bosh dhe elementi i shumicës ekziston gjithmonë në grup."
Një shembull: nëse hyrja jonë është [1, 1, 1, 1, 2, 3, 4] atëherë pragu ynë për elementin e shumicës do të jetë gjatësia (7) e ndarë me 2 që është e barabartë me 3.5.
Pra, çdo gjë më e madhe se 3.5 në numër do të jetë elementi ynë i shumicës. Meqenëse kemi katër 1 në grup, 1 është përgjigjja jonë.
Ne jemi të garantuar se do të ketë gjithmonë një element shumicë në grupin e dhënë, kështu që nuk duhet të shqetësohemi për të kontrolluar nëse nuk ka një element shumicë.
Kur mendoj për numërimin e elementeve në një grup, mendoj për ciklin. Një mënyrë jashtëzakonisht e thjeshtë për të mbajtur gjurmët se cili numër ka numrin më të lartë gjatë ciklit është të përdorni një hartë hash. Kjo është qasja e parë që do të provoj.
Le të fillojmë.
Pseudokodi:
Këtu është një listë e shkurtër e hapave të nevojshëm për të zbatuar zgjidhjen time të parë:
- Inicializoni një hartë të zbrazët
- Inicializoni një variabël shumica e pragut (nums.length / 2)
- Hapni numrat dhe vendosni secilin element me vlerën 1 nëse nuk është tashmë në Hartë
- Nëse elementi është tashmë në Hartë, rriteni vlerën e tij me 1
- Gjatë ciklit, kontrolloni nëse një vlerë është mbi pragun e shumicës, kthejeni atë element nëse është
E shkurtër dhe e ëmbël.
Kodi:
Zgjodha të kontrolloja për gjendjen e kthimit brenda ciklit for në mënyrë që të mund të dilja më shpejt nga funksioni në disa raste. Kjo nuk përmirëson kompleksitetin e rastit më të keq të kohës O(n), por është një optimizim për inpute më të mëdha dhe funksionon për të gjitha rastet e testimit të paraqitura në këtë kontekst.
Ne përdorëm një hapësirë shtesë në kujtesë këtu. Kompleksiteti i hapësirës është O(m) ku m është i barabartë me numrin e elementeve të dallueshëm në hyrjen numrat.
A ka ndonjë mënyrë për ta zgjidhur këtë problem në kohën O(n) pa përdorur hapësirë shtesë?
Një zgjidhje tjetër:
Nëse inicializojmë një ndryshore të synuar së bashku me një variabël numërimi, duhet të jemi në gjendje të mbajmë gjurmët e elementit të shumicës ndërsa kalojmë nëpër numrat.
Këtu janë hapat në pseudo-kodin:
- Inicializoni një ndryshore të synuar
- Inicializoni një variabël numërimi në 0
- Hapni numrat, nëse objektivi === nums[i] shtoni 1 për të numëruar
- Përndryshe nëse numërimi është 0, objektivi = numra[i]
- Përndryshe, zbrit 1 nga numërimi
- Ktheni objektivin
Këtu është kodi:
Kjo zgjidhje është e shkëlqyer për kontekstin e kësaj sfide. Ai nuk bën asgjë më shumë se çfarë duhet të bëjë, që është cikli dhe të mbajë gjurmët e elementit më të përsëritur në grupin e dhënë.
Meqenëse problemi garanton që gjithmonë do të ketë një element të shumicës, ne mund të fokusohemi vetëm në numërimin dhe mbajtjen e gjurmëve të elementit që ndodh më shumë.
Me një kompleksitet hapësinor prej O(1) duke ruajtur kompleksitetin kohor të O(n), kjo zgjidhje është një qasje elegante dhe më e thjeshtë për problemin e dhënë.
Më tregoni nëse keni një mënyrë tjetër për ta zgjidhur këtë sfidë ose nëse keni ndonjë këshillë për mua. Kujdesu!