zweitkleinster wert eines feldes?!
-
einfach ein c-feld oder vektor von typ float.
ob's jetzt ein float typ ist, ist nicht so wichtig.
nur wie ich den zweitkleinsten bekomme ist, wäre wichtig...
-
Das einzige was mir jetzt einfällt (finde die einfache Frage erstaunlich schwer) ist weder schön noch effektiv, und obs funzt weiß ich auch nicht, aber vielleicht besser als nichts:
float last_smallest = array[0]; float second_smallest = array[0]; int index_smallest = 0; for (int i = 1; i < size; ++i) { if (array[i] < last_smallest) { last_smallest = array[i]; index_smallest = i; } } for (int i = 1; i < size; ++i) { if ( (array[i] < second_smallest) && (i != index_smallest) ) second_smallest = array[i]; }
-
hört sich ziemlich plausibel/gut an. eigentlich hätte ich auch von selber drauf kommen können. aber so ist das ja immer.
danke!
-
ach so mich hat dein zusatz gleitkomma irgendwie irritiert...
template <class T> T second_min(T* a,int n){ T *p,*q; //pzeigt immer aufs kleinste q aufs zweitkleinste element p=a+1;q=a; if(*a<a[1]){p=a;q=a+1;} for(a+=2;--n-1;++a) if(*a<*p){q=p;p=a;} else if(*a<*q && *a!=*p)q=a; //falls bei doppelt vorkommen das zweitkleinste auch das kleinste sein soll die ungleichbedinung weglassen return *q; }
-
Hi windalf,
danke für deine antwort.
das ist natürlich die profilösung und mir daher nicht ganz verständlich.
kannst du mir da noch ein paar erklärungen geben ?!Windalf schrieb:
ach so mich hat dein zusatz gleitkomma irgendwie irritiert...
template <class T> -> was macht die klasse ? T second_min(T* a,int n){ //wie bekomme ich da nun mein float-feld rein? zeiger von a = anfang vom feld ? T *p,*q; p=a+1;q=a; if(*a<a[1]){p=a;q=a+1;} for(a+=2;--n-1;++a) //wie läuft das mit der bedingung ab ? mach N kleiner und dann nochmal mit kleiner mit -1 ? if(*a<*p){q=p;p=a;} else if(*a<*q && *a!=*p)q=a; return *q; }
-
ob das ne profilösung ist wage ich mal zu bezweifeln... auf jeden fall muss man nur einmal die schleife durchlaufen und es funzt mit allen zahlendatentypen
#include <iostream> template <class T> T second_min(T* a,int n){ T *p,*q; //pzeigt immer aufs kleinste q aufs zweitkleinste element p=a+1;q=a; if(*a<a[1]){p=a;q=a+1;} //check ob p aufs kleines element zeigt, wenn nein p und q tauschen for(a+=2;--n-1;++a) //n-2 mal die schleife durchlaufen if(*a<*p){q=p;p=a;} //wenn aktuelles element kleiner als das auf welches p zeigt dann p aufs aktuelle zeigen lassen und q auf p else if(*a<*q && *a!=*p)q=a; //sonst wenn aktuelles element kleiner als *q dann q auf a zeigen lassen... die bedingung *a!=*p wird nur gebraucht falls das kleinste element mehrfach vorkommt, an sonsten weglassen return *q; //q zurückliefern das aufs zweitkleinste element zeigt } int main(){ int a[]={7,5,3,3,4,6,7}; std::cout<<second_min(a,sizeof(a)/sizeof(*a))<<std::endl; double f[]={7.5,5.3,3.2,3.4,4.6,6.8,7.9}; std::cout<<second_min(f,sizeof(f)/sizeof(*f))<<std::endl; return 0; }
-
naja da ich das auch mal weiß geb ich meinen senf auch dazu:
du sortierst das ganze hast dann den kleinsten wert im element 0 und im element 1 den zweit kleinsten wert:
float array[7]; // Dein Feld int temp; // "Zwischenspeicher" for(int pos1 = 0; pos1 <=6; pos1++) { for(int pos2 = 0; pos2 <=6; pos2++) { if(tipps[pos1] < tipps[pos2]) { temp = tipps[pos1]; array[pos1] = tipps[pos2]; array[pos2] = temp; } } }
-
@longInt
der aufwand von deiner lösung ist viel zu hoch (quadratisch)... da kann man gleich einen qsort drüber laufen lassen und das zweite element nehmen der hat als erwartungswert nur n*log(n)...
-
Aber nicht im worst-case. Da stinkt Quicksort genauso ab.
-
Aber nicht im worst-case. Da stinkt Quicksort genauso ab.
aber wenns im schlechtesten fall so schlecht wie quadratisch ist ist es also automatisch besser...
-
/*headers*/ #include <vector> #include <algorithm> using namespace std; /*...*/ vector<float> fvec; /* insert values in fvec */ sort(&fvec[0],&fvec[fvec.size()-1]);jetzt ist in fvec[0] die kleinste,
und in fvec[1] die 2. kleinste, falls fvec[0]!=fvec[1];Devil
-
Dann nimmt man halt ein Sortierverfahren das immer n*log n hat zum Beispiel Mergesort. Aber ich glaube das n-th Element Problem ist sogar in O(log n) zu lösen, genauso wie der Median. Aber ich kenne den Algo dafür leider nicht.
-
kleine frage, großes problem ?!
danke für eure posts! hat mir echt weitergeholfen.
-
devil81 schrieb:
sort(&fvec[0],&fvec[fvec.size()-1]);Dabei wird das letzte Element nicht mitsortiert! Deswegen besser fvec.begin() und end() benutzen, dann können solche kleinen Fehler nicht passieren!