Finde fehlende Zahl
-
Hallo,
es soll die fehlende Zahl gefunden werden;
const int size = 10; int arr[size] = {0,1,2,3,5,6,7,8,9,10}; // die Zahl 4 fehlt int arr1[size+1]={0}; int fehlende_zahl = 0 ; for(int i = 0 ; i < size ; i++) { arr[i] = 1; } for(int i = 0 ; i < size+1 ; i++) { if( arr[i] == 0 ) {fehlende zahl = i ; break;} }Um die fehlende Zahl zu finden brauch ich ca 2n Rechenschritte. Wenn einer weiß wie es noch schneller geht , kann er es gerne posten.
ABer kann ich mir ehrlich gesagt nicht vorstellen
-
Dein Programm ist definitiv verkehrt (wenn auch leicht zu fixen). Außerdem ist
fehlende_zahl = 4;viel einfacher (Tipp: Gib die Aufgabenstellung exakt an.)
-
Bashar schrieb:
wenn auch leicht zu fixen
Na, so einfach ist das nun auch nicht. Nur Templates sind ausdrucksstark und vielseitig genug, um dies halbwegs übersichtlich zu lösen. Mein Vorschlag:
template <int I = 0, int i = 0> struct utility { static const int result = I + i; static const int greater = 43; static const int lesser = -1; typedef const int* ptr_t; template <typename T> T operator()(T t) { return t + I; } bool operator[](int ii) { return I == ii; } template <typename T> T operator/(T* t){ return *t; } }; template <int size, int done = 0> struct find_missing { int result; find_missing(typename utility<>::ptr_t current) : result ((utility<>() / this)(current)) { } operator int() { return result; } int operator()(typename utility<>::ptr_t current) { if (utility<done>()[utility<>() / current]) return find_missing<size, utility<done, 1>::result>(utility<1>()(current)); else return done; } }; template <> template <int size> struct find_missing<size, size>: public find_missing<utility<>::greater, utility<>::lesser> { find_missing(typename utility<>::ptr_t current): find_missing<utility<>::greater, utility<>::lesser>(current) { } int operator()(typename utility<>::ptr_t) { return size; } }; #include <iostream> int main() { const int size = 10; int arr[size] = {0,1,2,3,5,6,7,8,9,10}; // die Zahl 4 fehlt std::cout << find_missing<size>(arr) << '\n'; }
-
ABer kann ich mir ehrlich gesagt nicht vorstellen
Ich addiere alle Zahlen und vergleich mit dem kleinen Gauss (n*(n+1)/2 oder so). Zeit O(n), Platz O(1). Insgesamt wird's wesentlich schneller sein, aber miss selbst nach!
-
solange nur eine Zahl fehlt, gehts logarithmisch. ansonsten k*log(n) wobei k die Anzahl fehlender Zahlen und n die größe des arrays ist.
//edit als kleiner Denkanstoß:
In einem Teilarray a1,a2,a3,....,an fehlt kein Element, wenn an-a1=n ist.
-
Wie wäre es mit std::set_difference?
-
blurry333 schrieb:
ABer kann ich mir ehrlich gesagt nicht vorstellen
Ich kann mir nicht vorstellen, dass dein Code überhaupt funktioniert.
-
solange nur eine Zahl fehlt, gehts logarithmisch.
Blurry hat leider nichts spezifiziert. Prinzipiell kann nicht davon ausgegangen werden, dass die Zahlen sortiert sind. (Prinzipiell kann nicht davon ausgegangen werden, dass jede Zahl nur einfach enthalten ist).
-
Wieso nicht die offensichtlichste Lösung?
const int size = 10; int arr[size] = {0,1,2,3,5,6,7,8,9,10}; // die Zahl 4 fehlt int fehlende_zahl = 0; if (arr[0] == 0) { for (int i = 1; i < size; ++i) if (arr[i - 1] + 1 != arr[i]) { fehlende_zahl = i; break; } }Und schon hat man schlimmstenfalls O(n), meistens sogar besser.
-
ja mein Programm war etwas falsch. Aber ihr wußtet ja alle wie es gemeint war
const int size = 10; int arr[size] = {0,1,2,3,5,6,7,8,9,10}; // die Zahl 4 fehlt int arr1[size+1]={0}; int fehlende_zahl = 0 ; for(int i = 0 ; i < size ; i++) { arr1[arr[i]] = 1; } for(int i = 0 ; i < size+1 ; i++) { if( arr1[i] == 0 ) {fehlende_zahl = i ; break;} } cout<<fehlende_zahl;
-
Nathan schrieb:
Und schon hat man schlimmstenfalls O(n), meistens sogar besser.
Besser? Also O(log n) oder gar O(k)? Wie soll das bei einer linearen Suche (die du in deinem Code verwendest) gehen?
im Schnitt brauchst du n/2 Schritte -> O(n)
-
daddy_felix schrieb:
Nathan schrieb:
Und schon hat man schlimmstenfalls O(n), meistens sogar besser.
Besser? Also O(log n) oder gar O(k)? Wie soll das bei einer linearen Suche (die du in deinem Code verwendest) gehen?
im Schnitt brauchst du n/2 Schritte -> O(n)
Oh, stimmt, hab ich übersehen.
-
knivil schrieb:
ABer kann ich mir ehrlich gesagt nicht vorstellen
Ich addiere alle Zahlen und vergleich mit dem kleinen Gauss (n*(n+1)/2 oder so). Zeit O(n), Platz O(1). Insgesamt wird's wesentlich schneller sein, aber miss selbst nach!
Man kann auch xor verknüpfen und aus dem Ergebnis auf die fehlende Zahl schliessen - das war mal Genegstand einer Aufgabe von volkard in einem Wettbewerb. Da wurden die Zahlen auch 64bit groß und xor hat den Vorteil, dass (bei einem 32bit Rechner) die beiden Hälften der Zahlen unabhängig voneinander verarbeitet werden können, was bei Addition nicht der Fall ist. Dummerweise hat er auf einem C3 getestet (in-order, nur sehr beschränkt superskalar), so das das leider nicht zum Tragen kam.
