Zistite, či existuje číslo v poli, ktoré sa zobrazuje viac ako n / 8 krát - polia, algoritmus, výber, dátové štruktúry, časová zložitosť

Otázkou je:

Opíšte algoritmus, ktorý nájde v čase O (n), ak existuje pole n čísel, ktoré sa objavuje viac ako n / 8-krát.

Teraz mám odpoveď, ktorá je:

Vyberieme pre čísla na miestach: n / 9,2 * n / 9,3 * n / 9, ..., 8 * n / 9 a potom skontrolujeme, či sa jeden z týchto 8 kandidátov objaví aspoň n / 8 krát.

Ale nechápem, prečo by tento algoritmus fungoval.

Napríklad, zvážte nasledujúce pole: [3,3,1,3,2,3,4,3,5,3,6,3,7,3,8,3,9,3].

Takže tu n = 18, a ak je pre tento algoritmuskandidáti by boli 1,2,4,5,6,7,8,9 a keď skontrolujeme, či sa tieto čísla objavia aspoň n / 8-krát, odpoveď nebude, ale v skutočnosti pre 3 by odpoveď bola áno.

Takže nechápem, prečo je tento algoritmus správny ...

odpovede:

Kľúčovým poznatkom je, že vyberte najmäkeď sa kapitalizuje, má špeciálny význam: odkazuje na problém nájdenia k-tého najväčšieho záznamu v netriedenom poli. Možno trochu prekvapujúco a priori, to sa dá urobiť v lineárnom čase, napríklad pomocou stratégie medián 5 otáčania v kombinácii s algoritmom QuickSelect. Ak teda vyberiete položky s veľkými písmenami S a n / 9, 2n / 9, ... (náklady: 9 * lineárne - čo je lineárne), určite nájdete akékoľvek záznamy, ktoré sa vyskytnú n / 8-krát. Potom opakujte opakovanie vo svojom poli, aby ste spočítali počet výskytov každého z týchto kandidátov, a vyskúšajte, ako ste hotoví.