Lider prefiksowy

Question

Mam problem z osiągnięciem złożoności liniowej w tym zadaniu:

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(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 <= 500000) oznaczającą liczbę elementów ciągu. W drugim wierszu wejścia jest n liczb całkowitych a0,a1,...an-1(-10^9 <= ai <= 10^9) 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.

Przykład

Dla danych wejściowych:

9

3 4 5 3 3 1 3 3 3

Poprawną odpowiedzią jest:

3

Dodam, że wpadłem sam na rozwiązanie, które pokrywa się z tym wzorcowym ale tylko opisowo ;p

We wzorcowym rozwiązaniu złożoność wynosi O(n) a ja się na taką niestety nie umiem załapać. Nie chodzi mi o rozwiązanie tego zadania za mnie ale naprowadzenie mnie na lepszy pomysł.

Poniżej załączam kod:

#include <iostream>
#include <climits>

bool isLeader(int * arr, int n, int value)
{
    int result = 0;
    for(int i = 0; i < n; i++)
        if(arr[i] == value)
            result++;
    
    return result > n/2;
}

int findLeader(int * arr, int n)
{
    int value = 0;
    int multiplicity = 0;
    
    for(int i = 0; i < n; i++)
        if(multiplicity == 0)
        {
            multiplicity = 1;
            value = arr[i];
        }
        else
            if(arr[i] != value)
                multiplicity--;
            else
                multiplicity++;
    
    if(multiplicity > 0 && isLeader(arr, n, value))
        return value;
    else
        return INT_MAX;
}

void prefix_leader(int * arr, int n)
{
    int * leaders = new int[n];
    
    for(int i = 0; i < n; i++)
        leaders[i] = findLeader(arr, i+1);
    
    int leader = findLeader(leaders, n);
    
    if(leader != INT_MAX)
        std::cout << leader << std::endl;
    else
        std::cout << "NIE" << std::endl;
    
    delete [] leaders;
}

int main(int argc, const char * argv[]) {
    
    using namespace std;
    
    int n;
    cin >> n;
    
    int * arr = new int[n];
    for(int i = 0; i < n; i++)
        cin >> arr[i];
    
    prefix_leader(arr, n);
    
    
    
    return 0;
}

 

Answer 1

Nie moge teraz wpaść na jakieś rozwiązanie liniowe - możliwe, że jakieś jest. Ogarniam dwa podobne do siebie rozwiązania O(n * logn). Jedno z nich korzysta z dobrodziejstw mapy, a drugie z przenumerowania w O(n * logn) korzystajac z sortowania, oba przechodzą po tablicy od lewej do prawej i uzyskują lidera dla każdego prefixu w O(logn) w przypadku mapy i O(1) w tym z sortowaniem i przenumerowaniem wartosci, a potem... no prosiłeś bez spoilowania, więc... =)

Comments

Faktycznie mam już pomysł :D