Rekursion



  • Aber wenn man count für jedes einzelne Element anwendet, ist die Laufzeit O(N2).



  • schorsch code schrieb:

    Aber wenn man count für jedes einzelne Element anwendet, ist die Laufzeit O(N2).

    Das ist mir klar. Ich habe auch nicht behauptet, dass mein Vorschlag der Gipfel der Effizienz ist.

    Trotzdem ist eine uneffiziente Lösung besser als eine falsche 😉



  • MFK schrieb:

    schorsch code schrieb:

    Falls es nicht schlimm ist, wenn die Elemente im Ergebnis sortiert sind, kannst du es machen, wie in folgendem Beispiel:

    Er möchte doch nur die haben, die genau einmal vorkommen.

    Genau die hat er auch, wenn er den Code von schorsch code verwendet.



  • HumeSikkins schrieb:

    MFK schrieb:

    schorsch code schrieb:

    Falls es nicht schlimm ist, wenn die Elemente im Ergebnis sortiert sind, kannst du es machen, wie in folgendem Beispiel:

    Er möchte doch nur die haben, die genau einmal vorkommen.

    Genau die hat er auch, wenn er den Code von schorsch code verwendet.

    Nein, er hat dann auch "Hallo" und "blub", obwohl die mehr als einmal vorkommen.



  • MFK schrieb:

    Nein, er hat dann auch "Hallo" und "blub", obwohl die mehr als einmal vorkommen.

    Oh, stimmt. Da habe ich wohl nicht richtig gelesen.



  • schorsch code schrieb:

    Oh, stimmt. Da habe ich wohl nicht richtig gelesen.

    Ich musst auch mehrmals nachlesen, und bin mir immer noch nur fast sicher, was er will 🙂



  • schorsch code schrieb:

    MFK schrieb:

    Nein, er hat dann auch "Hallo" und "blub", obwohl die mehr als einmal vorkommen.

    Oh, stimmt. Da habe ich wohl nicht richtig gelesen.

    Ja. Da schließe ich mich dann mal an 😉

    Wenn etwas zusätzlicher Speicher nicht stört und n dann doch zu groß für einen n^2-Ansatz wird, kann man z.B. einfach noch eine Map<string,int> verwenden. Erster Durchlauf: Map initialisieren. Zweiter Durchlauf: alle Strings raushauen für die Map<string,int>::value_type.second > 1.



  • Oh, danke für reges Interesse. Also was ich möchte ist folgendes:

    z.B: Inhalt des Vektors ( eigentlich ca. 800 Elemente):
    "a"
    "b"
    "c"
    "a"
    "a"
    "b"

    Jetzt möchte ich alle mit allen vergleichen und die Element, die nur einmal vorkommen in einem neuen Vektor speichen. Hier wäre das "c".
    Die laufzeit möchte ich verbessern, indem wenn 2 gleiche gefunden werden, diese gelöscht werden. Wenn ich das hinbekommen habe, wäre ein nächster Schritt alle gleichen zu löschen. Also z.B: "a" kommt zum 2.Mal vor, dann werden alle a's gelöscht.

    Leider soll ich keine Bibliothek, STL Algorithmen benutzen.

    Kann mir jemand mit den zwei verschachtelten for-Schleifen weiterhelfen??

    schon mal vielen Dank



  • Erstmal ohne die Optimierung ("Die laufzeit möchte ich verbessern, indem wenn 2 gleiche gefunden werden, diese gelöscht werden"):

    for(int i=0;i<vec.size();++i)
    {
      bool anzahl=0;
      for(int j=0;j<vec.size()&&anzahl<2;++j)
      {
        if(vec[i]==vec[j])++anzahl;
      }
      if(anzahl==1) target.push_back(vec[i]);
    }
    

    Zur Optimierung würde ich eher schorch's Ansatz mit unique() weiterentwickeln (gerade wenn du am Anfang des vectors einen Wert löschst, kann das mehr Zeit in Anspruch nehmen als die Sache Wert ist):

    sort(vec.begin(),vec.end());//wenn du nicht mit der STL arbeiten willst, bau dir deine eigene Sortierung
    for(int i=0;i<vec.size();++i)
    {
      if(vec[i]!=vec[i+1])
        target.push_back(vec[i]);
      else
        while(vec[i]==vec[i+1]) ++i;
    }
    


  • Falls du außer vector noch andere Container verwenden darfst, befolge HumeSikkins' Vorschlag und nimm eine map:

    #include <iostream>
    #include <vector>
    #include <map>
    using namespace std;
    
    int main()
    {
        vector<string> test;
        test.push_back("Hallo");
        test.push_back("blub");
        test.push_back("bla");
        test.push_back("Hallo");
        test.push_back("blub");
        test.push_back("Hallo");
    
        map<string, int> heuristik;
        for(vector<string>::const_iterator iter = test.begin(); iter != test.end(); ++iter)
        {
            map<string, int>::iterator current = heuristik.find(*iter);
            if(current != heuristik.end())
                ++(*current).second;
            else
                heuristik.insert(make_pair(*iter, 1));
        }
    
        for(map<string, int>::const_iterator iter = heuristik.begin(); iter != heuristik.end(); ++iter)
            cout << (*iter).first << "\t" << (*iter).second << "\n";
    }
    


  • schorsch code schrieb:

    map<string, int>::iterator current = heuristik.find(*iter);
    if(current != heuristik.end())
      ++(*current).second;
    else
      heuristik.insert(make_pair(*iter, 1));
    }
    

    Also das könnte man noch kürzer schreiben 😃

    ++heuristik[*iter];
    

    (op[] legt ein neues Element mit Defaultwert (0) an, wenn es noch nicht existiert)



  • CStoll schrieb:

    op[] legt ein neues Element mit Defaultwert (0) an, wenn es noch nicht existiert

    Ah 💡, danke. Übrigens ist heuristik auch der falsche Name für die Variable; ich meinte eigentlich histogramm.



  • Ohne extra-Speicher und mit O(n log n) Zeitaufwand geht's mit sort und anschließendem manuellen drüberlaufen:

    flag keep auf true setzen, ertstes Wort einlesen.

    Jetzt immer das nächste Wort einlesen:
    - Ist es gleich dem zuvor gelesenen Wert, dann keep auf false
    - Ist es davon verschieden, dann: wenn keep true, dann in die rückgabeliste einfügen, sonst keep auf true setzen und zuletzt gelesenes Wort aktualisieren.

    Wenn man statt dem flag nen Zähler verwendet kann man so auch Wörter extrahieren, die genau x-mal oder weniger als x-mal vorkommen und solche Sachen.

    Am Ende der Daten ist natürlich etwas Vorsicht angebracht, sollte aber machbar sein.


Anmelden zum Antworten