Przywódca ciągu

Question

Witam ! 
Sprawa dotyczy znajdowania przywódcy danego ciągu jak w temacie, otóż: 
Mamy sobie jakiś ciąg n-wyrazowy. Podajemy k i słaby przywódca (jeden z nich) jest wtedy gdy występuje więcej niż n/k razy w danym ciągu. 

Oto algorytm znajdowania przywódcy w danym ciągu: 
 

#include <iostream>

using namespace std;

int main()
{
    int n = 0, k = 0;
    cin >> n >> k;

    //int n_przez_k = n / k; // slaby przywodca musi wystapic wiecej jak ta liczba w podadnym ciagu.

    cout << n / k << endl;

    int tab[n];
    for (int i = 0; i < n; i++)
    {
        cin >> tab[i];
    }

    cout << "Tablica ma postac: " << endl;
    for (int i = 0; i < n; i++)
    {
        cout << tab[i] << " ";
    }
    cout<<endl;

    int przywodca;
    int licz = 0;

    for (int i = 0; i < n; ++i)
    {
        if (licz == 0)
        {
            przywodca = tab[i];
            ++licz;
            cout << "licz: " << licz << endl;
        }
        else if (przywodca == tab[i])
        {
            ++licz;
            cout << "licz: " << licz << endl;
        }
        else
        {
            --licz;
            cout << "licz: " << licz << endl;
        }
    }

    //cout << endl;
    cout << "Przywodca to: " << przywodca << endl;

    return 0;
}

Zasada działania: Widząc nowy element zakładamy, że jest on przywódcą i liczymy, o ile razy więcej wystąpi w stosunku do pozostałych.

Ma to swoje wady, gdyż powiedzmy dla ciągu 1 2 3 4 5 6 7 nie ma przywódcy a program "wydrukuje" 7 gdyż w ostatniej iteracji to właśnie 7 będzie przywódcą. 
Moje pytanie to jak mogę uzależnić liczbę liczników przykładowych przywódców od zmiennej k, gdyż  wydaje mi się że to jest klucz w tym zadaniu. 
Zapraszam do pogadanki w komentarzach. 
Dziękuję za odpowiedzi !

Wesołych Świąt ! 

 

Answer 1

Rozwiązanie to użycie 2 elementów biblioteki standardowej C++:

https://en.cppreference.com/w/cpp/container/unordered_map - bo niepotrzebne Ci sortowanie

https://en.cppreference.com/w/cpp/algorithm/max_element - 3 rodzaj wywołania z komparatorem

Zamkniesz się w złożoności obliczeniowej O(n)

A jak nie wiesz jak to zaimplementować (lub nie możesz użyć), to poczytaj o tych rozwiązaniach abyś nie wymyślał koła na nowo.

Comments

Nie wiem, czy szukanie max elementu jest konieczne. Jeżeli założeniem jest to, że funkcja ma zwracać element dla którego liczba wystąpień jest większa od n/k to wystarczy na bieżąco sprawdzać czy ilość wystąpień jest większa od n/k. Wtedy w wielu przypadkach, nawet nie będzie trzeba iterować po elementach do końca.

---

Możliwe. Klasy algorytmu to nie zmieni. Założyłem że celem jest znalezienie najlepszego. Jeśli tylko słabego, wystarczy sprawdzać w trakcie inkrementacji wystąpienia.

---

Nie do końca wiem jak zastosować dobrze tą map-ę. Wiem natomiast że mapa musi być mniejsza bądź równa k

---

Jeśli dobrze zrozumiałem to robię map<int, int> pierwszy int to jest ograniczona przez wprowadzone k, a druga to zliczanie wystąpień poszczególnej liczby tak ?

---

Tak. Z tym że drugi int to raczej unsigned, i raczej nie std::map tylko std::unordered_map. std::map wykonuje przy każdym wstawieniu sortowanie po kluczu które jest tu Ci zupełnie zbędne.

---

OKay i to wszystko w pętli którą teraz mam, czy skasować ją i stworzyć coś innego ?

---

#include <unordered_map>
#include <iostream>

int main() {
    int data[] = { 1,2,3,4,5,3,3,3,4,2};
    std::unordered_map<int, unsigned> count;
    for (auto v: data) {
        count[v]++;
    }
    for (const auto& p: count) {
        std::cout << "key: " << p.first << ' '
            << "value: " << p.second << '\n';
    }
}

 

---

Kod się niestety nie kompiluje poprawnie :(

---

Czas użyć kompilatora wspierającego C++11. To już 8 lat na rynku jest. Masz kompilator starszy niż gcc 4.7.1 ? https://godbolt.org/z/Lbbq3q

Answer 2

Mam poważne wątpliwości, czy ten algorytm działa. Załóżmy tak:

-tablica składa się z elementów: 2,2,3,3,3,5,5

-k dobrane tak, że n/k =  2

A więc tak. Domniemamy, że '2' jest przywódcą. Po przejściu do 2 indeksu, mamy licz=2, przywodca=2. Potem po przejściu do 5 indeksu mamy tak, że licz=1, przywodca = 3. Na samym końcu mamy, że licz=1, przywodca=5 (o ile dobrze na szybko liczę i zrozumiałem twój algorytm). Więc teoretycznie nie ma żadnego przywódcy - praktycznie jest i jest to '3'.

Nie znam wszystkich założeń zadania. Nie wiem, czy w przypadku gdy jest więcej niż jeden przywódca, to mogę zwrócić jedną liczbę czy wszystkie? Na pętlach to bym do tego nie podchodził, bo żeby to na pętlach zrobić to algorytm miałby O(n^2) - w najgorszym przypadku. Podszedł bym do tego w najprostszy sposób. W Mapie<k,v> przechowywałbym ile razy (v) wystąpił element (k). W chwili gdy v będzie większe od n/k zwróciłbym v. Przeszedłbym też na funkcje, a nie pisał wszystko w mainie.

Comments

Mam zwrócić jednego z przywódców przywódców. Do tego mam właśnie wykorzystać algorytm wyżej. Jeśli chodzi o mapy to masz na myśli to :
http://www.cplusplus.com/reference/map/map/

---

Prawdopodobnie tak. W javie piszę, ale z tego co wiem w C++ też są mapy i też da się to zrobić na mapach

---

Okay poczytam o tym i jutro coś pokombinuję. Póki co dzięki :)