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ë:

  1. Inicializoni një hartë të zbrazët
  2. Inicializoni një variabël shumica e pragut (nums.length / 2)
  3. Hapni numrat dhe vendosni secilin element me vlerën 1 nëse nuk është tashmë në Hartë
  4. Nëse elementi është tashmë në Hartë, rriteni vlerën e tij me 1
  5. 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:

  1. Inicializoni një ndryshore të synuar
  2. Inicializoni një variabël numërimi në 0
  3. Hapni numrat, nëse objektivi === nums[i] shtoni 1 për të numëruar
  4. Përndryshe nëse numërimi është 0, objektivi = numra[i]
  5. Përndryshe, zbrit 1 nga numërimi
  6. 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!