Beiden höchsten Werter einer Zahlenreihe

Du bist neu in der Welt von C++? Dann schau hier herein!
Antworten
huckleberry
Beiträge: 115
Registriert: 2. Oktober 2010 17:07

Beiden höchsten Werter einer Zahlenreihe

Beitrag von huckleberry »

Hallo,

ich habe eine Zahlenreihe, ein Array. Ich möchte die beiden höchsten Werte in diesem Array mit den zugehörigen Indizes zurückgeben. Aktuell lege ich das ganze Array in einer MultiMap<Wert,Index> Paar ab, da diese sowieso geordnet werden.

Code: Alles auswählen

    QMultiMap<quint16, quint8> *ret_HighesValues = new QMultiMap<quint16, quint8>();

    for(int i = 0; i < array.size(); i++)
    {
        quint16 cur_value = array[i]:
        ret_HighesValues->insert(cur_value+1, i);
    }
    return ret_HighesValues;
Gibt es eine Datenstruktur, welche effizienter ist?

Mfg Huck
huckleberry
Beiträge: 115
Registriert: 2. Oktober 2010 17:07

Re: Beiden höchsten Werter einer Zahlenreihe

Beitrag von huckleberry »

Wie kehre ich die Sortierung nochmal um? Default ist aufsteigend, ich hätte gerne das größte key als erstes?
huckleberry
Beiträge: 115
Registriert: 2. Oktober 2010 17:07

Re: Beiden höchsten Werter einer Zahlenreihe

Beitrag von huckleberry »

Gelöst! Aber gibt es eine kompaktere Lösung?

Code: Alles auswählen

int dieerstenx = 0;
    QMultiMap<quint16, quint8>::const_iterator i = freq_map.constEnd();
    --i;

    while ( dieerstenx < 12 ) {
        quint16 key = i.key();
        quint8  val = i.value()+1;

        QString k = QString().sprintf("%02d", key).append("(");
        QString v = QString().sprintf("%02d", val).append(") ");

        line.append(v).append(k);

        i--;
        dieerstenx++;
    }
Mein line ist ein QString, welche in eine

Code: Alles auswählen

ui->textEdit->append( line );
QTextEdit ausgegeben wird. Geht es, dass nur beispielsweise das

Code: Alles auswählen

QString v;
fett eingetragen wird?
hilefoks
Beiträge: 144
Registriert: 13. März 2008 16:09

Re: Beiden höchsten Werter einer Zahlenreihe

Beitrag von hilefoks »

wenn ich dich richtig verstehe, hast du ein QArray oder ähnliches. Dieses enthält Integer in ungeordneter Reihenfolge. Du suchst den Index des größten bzw. kleinsten Wertes? Hier bietet sich std::max_element, std::min_element und std::distance an.

Code: Alles auswählen

#include <vector>
#include <iostream>
#include <algorithm>

int main() {
    std::vector<int> arr { 3, 7, 2, 5, 6, 4, 9};
    
    std::cout << "The smallest element is " << *std::min_element( arr.begin(), arr.end() ) 
              << " at index " << std::distance( arr.begin(), std::min_element( arr.begin(), arr.end() ) ) 
              << std::endl;

    std::cout << "The largest element is "  << *std::max_element(arr.begin(), arr.end() )
              << " at index " << std::distance( arr.begin(), std::max_element( arr.begin(), arr.end() ) ) 
              << std::endl;
}

MfG,
Hilefoks
huckleberry
Beiträge: 115
Registriert: 2. Oktober 2010 17:07

Re: Beiden höchsten Werter einer Zahlenreihe

Beitrag von huckleberry »

hilefoks hat geschrieben:wenn ich dich richtig verstehe, hast du ein QArray oder ähnliches.
Richtig.
hilefoks hat geschrieben:Dieses enthält Integer in ungeordneter Reihenfolge.
Richtig.
hilefoks hat geschrieben:Du suchst den Index des größten bzw. kleinsten Wertes?
Ich suche die beiden größten; in deinem Code beipsielsweise die 9 und die 7.
hilefoks
Beiträge: 144
Registriert: 13. März 2008 16:09

Re: Beiden höchsten Werter einer Zahlenreihe

Beitrag von hilefoks »

Ok, auch kein Problem:

Code: Alles auswählen

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> arr{ 3, 7, 2, 5, 6, 4, 9 };

    auto first = arr.cbegin();
    auto second = arr.cbegin();

    for( auto it = first; it != arr.cend(); ++it) {
        if( *it > *first ) {     // if the current value is greater than the already stored:
            second = first;      //  then the previous largest value is now the second largest
            first = it;          //  and the current is the new largest
        }
        else if( *it > *second ) {  // if the current value is greater than the stored second largest
            second = it;
        }
    }

   std::cout << "The largest element is " << *first << " at index " << std::distance( arr.cbegin(), first ) << std::endl;
   std::cout << "The second largest element is " << *second << " at index " << std::distance( arr.cbegin(), second ) << std::endl;
}
Achtung: Es fehlt noch jede Fehlerbehandlung! Außerdem gibt diese Implementierung bei einem Array { 2, 1, 2 } die Werte 2 und 1 zurück. Ob das gewollt ist, hängt natürlich vom Anwendungsfall ab.

MfG,
Hilefoks
nebler
Beiträge: 51
Registriert: 9. Juli 2009 15:26

Re: Beiden höchsten Werter einer Zahlenreihe

Beitrag von nebler »

@Hilefoks: Ist das Schlüsselwort auto von dem neuen C++ Standard?
Antworten