Problem z zadniem Lider prefiksowy

Question

Cześć robię takie zadanie:

Liderem nazywamy element, który występuje więcej niż k /2 razy, gdzie k jest liczbą rozpatrywanych elementów. Liderem prefiksowym nazywamy element, który jest liderem w więcej niż n/2 prefiksach rozpatrywanego ciągu, gdzie prefiks to każde i początkowych elementów ciągu (1 <= i <= n). Należy znaleźć wartość lidera prefiksowego dla zadanego ciągu.

Wejście Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą n (1 <= n ¬<=500 000) oznaczającą liczbę elementów ciągu. W drugim wierszu wejścia jest n liczb całkowitych a0, a1, . . . , an−1 (−109 <=ai <= 109 ), gdzie ai oznacza i-ty element ciągu.

Wyjście Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą równą wartości lidera prefiksowego lub jedno słowo NIE, jeśli lider prefiksowy nie istnieje.

Mój kod nie przechodzi kilku testów, pomoże mi ktoś zrozumieć dlaczego ? Czy może istnieć lider prefiksowy który nie jest liderem całego ciągu ? Proszę o pomoc :D

MÓJ KOD

Program sprawdzam TUTAJ

Answer 1

Lider prefiksowy niekoniecznie jest liderem całego ciągu. Dla takich wartosci:

2 2 2 1 1 1 1

cyfra 1 jest liderem całego ciągu, ale cyfra 2 jest liderem prefiksowym.

Więc lepiej by było wyznaczyć na początku wszystkich liderów prefiksowych i sprawdzić czy któryś z nich występuje więcej niż n/2 razy. Wyznaczanie liderów dla wszystkich prefiksów można prosto rozwiązać za pomocą stosu