Sprawdzania obecności zmiennej w vectorze.

0

Dzień dobry, chciałem się dowiedzieć czy jest jakiś inny sposób na sprawdzenie czy X jest w vectorze niż na pętli.

1

W bibliotece standardowej jest find, ale jeśli chodzi Ci o szybszy sposób, to nie ma, złożoność wyszukiwania liniowego jest zawsze n.

0

p = std::find (myints, myints+4, 30); 30 oznacza liczbe szukaną?

0

@KomnatoMan:

  1. a może potrzebujesz innej struktury danych, np std::map?
  2. Hipotetycznie, gdyby to było na wskaźnikach / referencjach to typu danych, można by myśleć o dualnym kontenerze

na pewno sa liczne biblioteki poza std:: do twojego zagadnienia

1

Jeśli elementy są nieuporządkowane to raczej nie ma innego wyjścia, niż przejść po elementach w O(n).

Co innego, gdyby był uporządkowany, bo wtedy mógłbyś wykorzystać wyszukiwanie binarne w O(logn).

Wydaje mi się, że znając rozkład wartości dało się nawet zejść do O(loglogn) czy jakoś tak, przynajmniej optymistycznie.

A gdybyś zamiast wektora mógł użyć zbioru wartości (zależy co z nim jeszcze robisz, poza szukaniem elementów) z czymś pokroju hash table pod spodem, to miałbyś znajdowanie elementu w O(1) ;)

0

@AnyKtokolwiek:
Nie znam std::map i nie mam pojęcie jak działa.
A jeśli chodzi o zadanie to (http://szkopul.edu.pl/problem[...]X_GbP-kiD/site/?key=statement)
i warto zauważyć że w pewnym momencie pojawia się cykl, ale można go użyć tylko wtedy gdy X==2,4,8,16,14,10.

0

Czy cykl występuje też dla cyfr 3, 5, 6, 7, 9? Jeśli tak to czy wszystkie liczby można znormalizować do cyklu? Jeśli tak to tutaj nie potrzeba tablicy a dzielenie modulo.

0

@lubie_programowac: takie rozwiązanie jest za wolne, dla tego zadania

0

Na razie takie coś wyszło, ale czy może zmienić p=find (t,t+N,X); ponieważ ten element zgłasza błąd o złym operatorze.

#include <iostream>
#include <vector>
using namespace std;
int suma(long long X)
{
    int wynik=0;
    while(X!=0);{
        wynik = wynik + X%10;
        X=X/10;
    }
    return wynik;
}
int main()
{
    ios_base::sync_with_stdio(0);
    int N,X,p;
    cin >> N >> X;
    int A=X;
    if(N==1){
        cout << X;
    }
    else{
        X=suma(X)*2;
        vector <int> t={2,4,8,16,14,10};
        p=find (t,t+N,X);
        if(p==X){
            cout << t[(N-2)%6];
            break;
        }
        else{
            for(int i =2;i<=N;i++){
                A=suma(A)*2;
            }
            cout << A;
            break;
        }
    }

    return 0;
}
0

Sugerowałbym użycie vector<size_t> used(18*9*2+1);
Zaznaczasz w tym wektorze elementy które już były oprócz elementu pierwszego jeżeli jest poza zakresem.
used[wartość]=numer;

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0