Szukanie par w tablicy- algorytm

Question

Hej,

mam zadanie w którym mam podaną tablicę n elementów, w której zawarte są liczby. Moim zadaniem jest sprawdzić ile jest par w takiej tablicy. Przykładowo ar[5]={1,3,1,2,3}; i mamy 2 pary (2x 1 i 2x 3). Kompletnie nie wiem jak ugryźć to zadanie. Próbowałem sortować tablicę i za pomocą ifów porównywać każdą liczbę ale coś mi nie idzie, i wydaje mi się że to zły sposób... Jest na to jakiś sprawdzony algorytm? 

Będę wdzięczny za wszelkie wskazówki.

Oto mój kod:

int sockMerchant(int n, vector<int> ar) {
    for(int i=1; i<n; i++)
    {
        for(int j=n-1; j>=1; j--)
        {
            if(ar[j]<ar[j-1])
            {
                int bufor;
                bufor=ar[j-1];
                ar[j-1]=ar[j];
                ar[j]=bufor;
            }
        }
    }
    int para=0;
    int z=0;
    for(int i=0;i<n-i;i++)
    {
        if(ar[i]==ar[i+1]) {
para=para+1;
        i++;}
    }
    return para;
 
}

Pozdrawiam,

Comments

https://www.geeksforgeeks.org/find-pairs-b-array-b-k/

---

Ok, a czy można to zrobić na poziomie elementarnym na jakim ja jestem w tej chwili? ;D

Na stronie którą wysłałeś jest pełno działań których jeszcze nie znam- push itp.

Robię sobie zadania z hacerrank.com i zastanawiam się czy nie dotarłem do etapu który wykracza poza moja wiedzę- choć to zadanie jest na poziomie "easy"

---

Jakaś konkretna złożoność jest wymagana?

---

Powiedzmy że na podstawie mojego kodu.

---

Nie musisz przesyłać osobno rozmiaru dla wektora. std::vector ma taką metodę jak size, która zwraca rozmiar kontenera. Możesz spróbować zaimplementować to metodą siłową, złożoność będzie okropna, ale będzie to trywialne.

Answer 1

Można to łatwo zrobić używając asocjacyjnego kontenera map<> , który znajduje się w STL. Wymagany jest minimum C++11.

#include <iostream>
#include <vector>
#include <map>

using namespace std;

map<int,int> findPairs( const vector<int>& data )
{
    map<int,int> result;

    for( const auto& element : data )
    {
        ++result[element];
    }

    return result;
}

int main()
{
    vector<int> data {2,6,6,6,4,5,1,1,5,6,1,1,7,8,34,2,7,134,91,6,92,6,88,6,0,6};

    for( auto& value : findPairs(data) )
    {
        cout << " Number " << value.first << " has " << value.second/2 << " pairs." << endl;
    }

    return 0;
}

 

Comments

Pytanie brzmiało....

...Moim zadaniem jest sprawdzić ile jest par w takiej tablicy. Przykładowo ar[5]={1,3,1,2,3}; i mamy 2 pary (2x 1 i 2x 3)....

Zastanawiam się dlaczego nie użyjecie std::unordered_set(...) (BTW to jedno z przykładowych zadań w czasie rekrutacji Google).

---

@j23,  ... i będzie szybciej.

To wszystko nie jest takie proste i zależy od zestawu danych. Dla dużej liczby powtarzających się elementów unordered_map czy też unordered_multiset będą zdecydowanie lepszym rozwiązanie Zobacz

---

Oczywiście, że zależy. Fakt, testowałem dla szerszego zakresu liczb i tu moja wersja była sporo szybsza.

Dziwny ten twój test - dwa razy liczysz czasy dla unordered_map. Dodatkowo dostaję timeouta (liczy tylko dla findPairs2). Tu masz nieco lepiej zrobiony test -> link (Przejdź do Quick-bench).

---

To jeszcze jeden przykład na to, że nazwy funkcji nie powinny różnić się od siebie tylko jedną cyfrą, bo można się nieźle naciąć.

---

To fakt ;)