java aufgabe

[Heyoka955]

There is an array with some numbers. All numbers are equal except for one. Try to find it!

Kata.findUniq(new double[]{ 1, 1, 1, 2, 1, 1 }); // => 2
Kata.findUniq(new double[]{ 0, 0, 0.55, 0, 0 }); // => 0.55

It’s guaranteed that array contains more than 3 numbers.

The tests contain some very huge arrays, so think about performance.


kann mir einer erklären wie ich daran gehen muss. Ich habe als erstes das Array sortiert und danach weiß ich auch nicht mehr weiter. Ich weiß dass es eine Datensturktur gibt, die den einzigen Wert rausspuckt aber leider weiß ich nicht mehr ob das hashset oder hashmap ist?
ich sitze fast 2 stunden daran.

 

[mihe7]

kann mir einer erklären wie ich daran gehen muss.

Klar: Nachdenken - ohne Code. Du brauchst hierfür überhaupt keine Datenstruktur außer das Array.

Überleg Dir doch mal, welche Fälle es bei einem Array mit 3 Elementen gibt und dann überlegst Du Dir wie es aussieht, wenn Du ein Element dazunimmst.

 

[Heyoka955]

Klar: Nachdenken - ohne Code. Du brauchst hierfür überhaupt keine Datenstruktur außer das Array.

Überleg Dir doch mal, welche Fälle es bei einem Array mit 3 Elementen gibt und dann überlegst Du Dir wie es aussieht, wenn Du ein Element dazunimmst.

Brauche ich einen boolean dafür ? Wäre guter tipp?

 

[mihe7]

Du brauchst erstmal gar nichts, was mit (Java-)Programmierung zu tun hat.

Machen wir es mal anders: wenn das erste Element des Arrays garantiert nicht das gesuchte Element ist, wie würdest Du vorgehen?

 

[Heyoka955]

   Arrays.sort(arr);
      
      if(arr.length == 3){
        for(int i = 1; i < arr.length; i++){
          if(arr[i] == arr[i-1]){ break; } //falls gleich sind dann beenden wir die ausführung und erhöhen i
          if(arr[i] != arr[i-1]){ return arr[i]; }
        
        }
      
      }

Du brauchst erstmal gar nichts, was mit (Java-)Programmierung zu tun hat.

Machen wir es mal anders: wenn das erste Element des Arrays garantiert nicht das gesuchte Element ist, wie würdest Du vorgehen?

ich habe drei Elemente das heißt eins ist eiinzel.
Dann würde ich vom ersten aus den zweiten vergleichen und auf gleichheit prüfen und wenn die nicht gleich sind dann weiß ich dass meine zahl ist aber wenn sie gleich sind dann gehe ich zur nächsten zahl. Das ist nur ein Fall für drei Elemente.

aber falls ich n elemene habe dann muss ich anders vorgehen, nehmen wir an ich habe 0 0 2 5 5 und ich bin bei der Stelle wo ich 0 mit zwei vergleiche und ich weiß dass beide zahlen unterchiedlich sind dann muss ich in dem falle den nachfolger von der zwei abfragen um zu wissen ob die zwei nicht identisch sind.

 

[mrBrown]

Du kannst das Array mit N Elementen auf drei Elemente reduzieren.

Du betrachtest immer drei Elemente:
Entweder eines der drei Elemente unique, dann bist du fertig.
Oder alle drei sind gleich, dann musst du drei andere Elemente betrachten.

Die Auswahl der drei Elemente liegt jetzt noch bei dir...

nehmen wir an ich habe 0 0 2 5 5

"All numbers are equal except for one", tritt also nicht ein.


(BTW, dein Code ist ziemlicher Unsinn. Angefangen von sort, über die Schleife bis hin zum break...)

 

[mrBrown]

Amüsant, aus dem Test-Code von codewars zu diesem Kata:

Try to create as huge array as possible. It is very good,
if solutions with sort will fail on timeout.
Do it to force people use O(n) solutions

Die am besten ("best practice" und "clever") bewertete Lösung:

///...
Arrays.sort(arr);
// ...

 

[Heyoka955]

}
}

Du kannst das Array mit N Elementen auf drei Elemente reduzieren.

Du betrachtest immer drei Elemente:
Entweder eines der drei Elemente unique, dann bist du fertig.
Oder alle drei sind gleich, dann musst du drei andere Elemente betrachten.

Die Auswahl der drei Elemente liegt jetzt noch bei dir...



"All numbers are equal except for one", tritt also nicht ein.


(BTW, dein Code ist ziemlicher Unsinn. Angefangen von sort, über die Schleife bis hin zum break...)

Du kannst das Array mit N Elementen auf drei Elemente reduzieren.

Du betrachtest immer drei Elemente:
Entweder eines der drei Elemente unique, dann bist du fertig.
Oder alle drei sind gleich, dann musst du drei andere Elemente betrachten.

Die Auswahl der drei Elemente liegt jetzt noch bei dir...



"All numbers are equal except for one", tritt also nicht ein.


(BTW, dein Code ist ziemlicher Unsinn. Angefangen von sort, über die Schleife bis hin zum break...)

jabe den Code geändert, jetzt funktionierte er für den falle von n gleich 3 aber ich habe n elemente gegeben. das ist eine aufgabe von codwars

 

[mrBrown]

jabe den Code geändert, jetzt funktionierte er für den falle von n gleich 3 aber ich habe n elemente gegeben. das ist eine aufgabe von codwars

Zeigst du den Code auch?

 

[httpdigest]

ich sitze fast 2 stunden daran.

Du meinst wohl 2 Monate. Schau mal in deine Gespräche-Historie, als du bereits am 27. Januar 2019 um Hilfe mit dieser exakten Aufgabe gebeten hast und ich dir genau dieselbe Strategie wie @mrBrown bei https://www.java-forum.org/thema/java-aufgabe.184484/#post-1179132 vorgeschlagen habe. Das ganze haben wir schon ausschweifend diskutiert.

 

[Heyoka955]

Du kannst das Array mit N Elementen auf drei Elemente reduzieren.

Du betrachtest immer drei Elemente:
Entweder eines der drei Elemente unique, dann bist du fertig.
Oder alle drei sind gleich, dann musst du drei andere Elemente betrachten.

Die Auswahl der drei Elemente liegt jetzt noch bei dir...



"All numbers are equal except for one", tritt also nicht ein.


(BTW, dein Code ist ziemlicher Unsinn. Angefangen von sort, über die Schleife bis hin zum break...)

verstehe also ich bekome erstmal von den drei den einen Wert raus, der nur einmal vorkam nachdem ich das gemacht habe, mache ich eine weitere for schleife ab der Stelle wo dieser wert unique ist in dem dreierbereich und vergleiche drei weitere ? aber wie weißt ich wie lang das Array ist? ich muss das dann so oft machen bis zum ende des Array.

 

[Heyoka955]

Zeigst du den Code auch?

Array.sort(array);

for(int i = 1; i < array.length; i++){
    if(array[i]==array[i-1]) return a[2];
    else {
        return array[i-1];
    }
    
    
}

 

[mrBrown]

verstehe also ich bekome erstmal von den drei den einen Wert raus, der nur einmal vorkam

*Wenn* ein Wert in den dreien nur einmal vorkommt, bist du fertig. Da gibt es kein "nachdem".

Du musst nur weitere Elemente betrachten, wenn drei Werte gleich sind.

aber wie weißt ich wie lang das Array ist? ich muss das dann so oft machen bis zum ende des Array.

So lange probieren, bis du den kleinsten Index findest, der eine IndexOutOfBoundException wirft (oder halt einfach [/icode]length[/icode] benutzen...)

 

[mrBrown]

Du meinst wohl 2 Monate. Schau mal in deine Gespräche-Historie, als du bereits am 27. Januar 2019 um Hilfe mit dieser exakten Aufgabe gebeten hast und ich dir genau dieselbe Strategie wie @Robat bei https://www.java-forum.org/thema/java-aufgabe.184484/#post-1179132 vorgeschlagen habe. Das ganze haben wir schon ausschweifend diskutiert.

Hast du den falschen Beitrag oder die falsche Person verlinkt oder versteh ich nur nicht was du meinst?

 

[mrBrown]

Array.sort(array);

for(int i = 1; i < array.length; i++){
    if(array[i]==array[i-1]) return a[2];
    else {
        return array[i-1];
    }
  
  
}

Jetzt guck dir deinen Code noch mal genauer an:

Ist das sort sinnvoll?
Wie lange läuft die Schleife (aka, welche i werden im Schleifenkörper benutzt)? (Probiere es mit dem Debugger aus, wenn du nicht selbst drauf kommst...)

 

[httpdigest]

Hast du den falschen Beitrag oder die falsche Person verlinkt oder versteh ich nur nicht was du meinst?

Ups. Sorry! Ich meinte natürlich dich, also @mrBrown :-D (im ursprünglichen Post korrigiert)

 

[Heyoka955]

Hast du den falschen Beitrag oder die falsche Person verlinkt oder versteh ich nur nicht was du meinst?

Was ein Stalker hahah, wieso macht codewars das so dass man erledigte aufgaben neu machen muss?

 

[mrBrown]

Was ein Stalker hahah, wieso macht codewars das so dass man erledigte aufgaben neu machen muss?

Weil man Katas regelmäßig wiederholen soll. Wie du siehst, hat das ja auch seinen Grund...

 

[Heyoka955]

was soll ich machen wegen der aufgabe? aber was ist wenn sagen wir ich habe 2 2 2 3 3 4
wenn ich das in drei aufteile dann habe ich 2 2 2 als dreier Array aber wie soll ich dann da die zahl herausfinden?

 

[Heyoka955]

Weil man Katas regelmäßig wiederholen soll. Wie du siehst, hat das ja auch seinen Grund...

Weil man Katas regelmäßig wiederholen soll. Wie du siehst, hat das ja auch seinen Grund...

Array.sort(array);

for(int i = 1; i < array.length; i++){
    if(array[i]==array[i-1]) return a[2];
    else {
        return array[i-1];
    }
    
    
}


also wie sieht das mit dem code aus? der funktioniert für array länge 3

 

[httpdigest]

was soll ich machen wegen der aufgabe? aber was ist wenn sagen wir ich habe 2 2 2 3 3 4
wenn ich das in drei aufteile dann habe ich 2 2 2 als dreier Array aber wie soll ich dann da die zahl herausfinden?

All numbers are equal except for one.

 

[mrBrown]

was soll ich machen wegen der aufgabe? aber was ist wenn sagen wir ich habe 2 2 2 3 3 4
wenn ich das in drei aufteile dann habe ich 2 2 2 als dreier Array aber wie soll ich dann da die zahl herausfinden?

So ein Array kommt nicht vor. Wie schon mal aus der Aufgabenstellung zitiert: "All numbers are equal except for one".

 

[mrBrown]

Array.sort(array);

for(int i = 1; i < array.length; i++){
    if(array[i]==array[i-1]) return a[2];
    else {
        return array[i-1];
    }
   
   
}


also wie sieht das mit dem code aus? der funktioniert für array länge 3

Noch mals:

Jetzt guck dir deinen Code noch mal genauer an:

Ist das sort sinnvoll?
Wie lange läuft die Schleife (aka, welche i werden im Schleifenkörper benutzt)? (Probiere es mit dem Debugger aus, wenn du nicht selbst drauf kommst...)

 

[Heyoka955]

Noch mals:

arbeite ohne Debugger alles per Gedanken un dpapier versuche ich das nachzuvollziehen. Also wieso sollte das sort nicht sinnv

Noch mals:

du musst genauer sprechen, verstehe nicht was du genau meinst? die schleife fängt ab index 1 und vergleicht index 0

 

[mrBrown]

Also wieso sollte das sort nicht sinnv

Weil das sortieren nicht nötig ist, das ganze nur langsamer macht, und für deine Code einfach genau gar keine Rolle spielt.

arbeite ohne Debugger alles per Gedanken un dpapier versuche ich das nachzuvollziehen. [...] du musst genauer sprechen, verstehe nicht was du genau meinst? die schleife fängt ab index 1 und vergleicht index 0

Mach einen Schreibtischtest:
Welche Werte nimmt i innerhalb des Schleifenkörpers an? (Du solltest anfangen, Code zu schreiben, den du auch verstehst )

 

[Heyoka955]

for(int i = 2; i < a.length; i++){
    if(a[i] == a[i-1] && a[i] != a[i-2]) return a[i-2];
    else if(a[i] != a[i-1]) && a[i] == a[i-2]) return a[-1];
    else {
       
        return a[i];
    }
}              
   
   
   
}

habe das soeben gemacht, ich dachte vorher in der aufgabe würden alle arten von zahlen vorkommen aber nur eine zahl einmalig daher hatte ich probleme, habe den Code am Schreibtisch ausgetestest, der funktioniert glaube ich

 

[httpdigest]

Nope. Spiele dein Beispiel mal mit dem Array [1, 1, 1, 2] durch. Du brauchst nur die allererste Schleifeniteration (also mit i=2) durchzuspielen.

 

[Heyoka955]

Nope. Spiele dein Beispiel mal mit dem Array [1, 1, 1, 2] durch. Du brauchst nur die allererste Schleifeniteration (also mit i=2) durchzuspielen.

Okay was kann ich da noch tun

 

[mihe7]

@Heyoka955 Jetzt schmeiß endlich den Code weg und denk halt mal für fünf Minuten nach.

 

[Heyoka955]

@Heyoka955 Jetzt schmeiß endlich den Code weg und denk halt mal für fünf Minuten nach.

Ich kann nicht mehr. Jede Hirnzelle ist verbrannt.

Ich verstehe nicht wieso mein Algorithmisches denken so schlecht ist...

 

[mihe7]

Ich verstehe nicht wieso mein Algorithmisches denken so schlecht ist...

Weil Du vermutlich sofort meinst, Code schreiben zu müssen.

 

[httpdigest]

Ich verstehe nicht wieso mein Algorithmisches denken so schlecht ist...

Das erfordert Übung. Viel Übung. Seeeehr viel Übung. Viele viele Jahre.

 

[Heyoka955]

Weil Du vermutlich sofort meinst, Code schreiben zu müssen.

Ich habe davor nachgedacht, ich schaffe es immer nur paar Fälle abzudecken aber nie alle.

 

[Heyoka955]

Weil Du vermutlich sofort meinst, Code schreiben zu müssen.

Ich habe davor nachgedacht, ich schaffe es immer nur paar Fälle abzudecken aber nie alle.

 

[Heyoka955]

Das erfordert Übung. Viel Übung. Seeeehr viel Übung. Viele viele Jahre.

Ich habe jetzt bald professionelle Software Entwicklung und wir fangen da mit Projekte an. Daher will ich mich vorbereiten.
Äußeren will ich auch als Werkstudent im Unternehmen als Java Entwickler arbeiten aber mit diesen Skills ...

 

[httpdigest]

Ich habe jetzt bald professionelle Software Entwicklung.

Was soll denn das heißen? Vorher hattet ihr nur amateurhafte Software-Entwicklung, oder wie? Oder heißt die Vorlesung/Übung einfach nur so...

 

[Heyoka955]

Was soll denn das heißen? Vorher hattet ihr nur amateurhafte Software-Entwicklung, oder wie? Oder heißt die Vorlesung/Übung einfach nur so...

Also Einführung in Programmierung hieß das, und jetzt kommt das was ich eben meinte. Wir arbeiten mit github
4 vier Projekte und 4 übingsblätrer. die heist die Vorlesung also profesionelle Software Entwicklung programmierpraktikum 1
Naja kann mir einer helfen bei der Lösung der Aufgabe

 

[httpdigest]

Naja kann mir einer helfen bei der Lösung der Aufgabe

Ehrlich gesagt glaube ich das nicht. Außerdem wurde dir bereits viel gehofen. Die nächste "Ebene" von "Hilfe" wäre, dir den Algorithmus Schritt für Schritt in Prosa aufzuschreiben und der finale Schritt von "Helfen" wäre, eine funktionierende Lösung zu präsentieren.

 

[Heyoka955]

Was soll denn das heißen? Vorher hattet ihr nur amateurhafte Software-Entwicklung, oder wie? Oder heißt die Vorlesung/Übung einfach nur so... "Professionell" darf es nur heißen, wenn du das auch als Profession machst (also im Beruf).

okay verstehe, was meinst du mit glauben?

 

[mihe7]

Naja kann mir einer helfen bei der Lösung der Aufgabe

Was glaubst Du, was hier alle versuchen? Das Problem ist, dass es bei Dir "Klick machen" muss. Daher wird Dir keiner eine Lösung hinschreiben. Wir können Dir nur einen Schubser geben.

Also, probieren wir es nochmal mit der vereinfachten Variante: Du hast eine Liste von beliebig vielen Zahlen. Jede dieser Zahlen - bis auf eine - ist identisch mit der ersten Zahl der Liste. Aufgabe: finde die einzige Zahl, die nicht mit den anderen Zahlen der Liste übereinstimmt.

Wie gehst Du vor? (Kein Code, einfach nur die Vorgehensweise beschreiben)

 

[Heyoka955]

Was glaubst Du, was hier alle versuchen? Das Problem ist, dass es bei Dir "Klick machen" muss. Daher wird Dir keiner eine Lösung hinschreiben. Wir können Dir nur einen Schubser geben.

Also, probieren wir es nochmal mit der vereinfachten Variante: Du hast eine Liste von beliebig vielen Zahlen. Jede dieser Zahlen - bis auf eine - ist identisch mit der ersten Zahl der Liste. Aufgabe: finde die einzige Zahl, die nicht mit den anderen Zahlen der Liste übereinstimmt.

Wie gehst Du vor? (Kein Code, einfach nur die Vorgehensweise beschreiben)

also ich vergleiche die werte als erstes ich vergleiche die erst eziffer mit der zweiten und wenn sie gleich sind dann gehe ich weiter und vergleiche die erste mit der dritten und wenn sie gleich sind dann gehe ich weiter und dann vergleiche ich die erste mit der vierten und wenn sie ungleich sind dann printe ich das Ergebnis bzw ich kenne das Ergebnis.

 

[httpdigest]

ich vergleiche die erste ziffer mit der zweiten und wenn sie gleich sind dann gehe ich weiter ... und wenn sie ungleich sind dann printe ich das Ergebnis bzw ich kenne das Ergebnis.

Dein Algorithmus ist noch zu unpräzise. Wenn die Ziffern ungleich sind, welcher ist denn dann der gesuchte Wert?

 

[Heyoka955]

Dein Algorithmus ist noch zu unpräzise. Wenn die Ziffern ungleich sind, welcher ist denn dann der gesuchte Wert?

der wert mit dem verglichen wurde als j, wegen der doppelt for schleife

 

[httpdigest]

Was für ein j und was für eine doppelte for-Schleife? Deine Aussage macht keinen Sinn.

 

[mihe7]

der wert mit dem verglichen wurde als j, wegen der doppelt for schleife

Nein, nein, nein, kein Code. Bleib bei Deiner Beschreibung.

 

[Heyoka955]

Nein, nein, nein, kein Code. Bleib bei Deiner Beschreibung.

Ich verlgleiche die erste Ziffer mit dem wert wo der Wert nicht mehr gleich ist und wenn die ungleich sind weiß ich okay die verglichene Zahl also nicht Die erste Ziffer ist meine Zahl die ich suche.

 

[mihe7]

Gut, damit kann man leben Jetzt musst Du nur noch herausfinden, ob die erste Zahl diejenige ist, die sich ständig wiederholt (dann kannst Du Deinen Algorithmus anwenden) oder ob die erste Zahl die gesuchte Zahl ist (dann hättest Du die Zahl sofort gefunden).

Wie viele Zahlen aus der Liste benötigst Du, um mit Sicherheit sagen zu können, ob die erste Zahl die gesuchte ist oder nicht? Mit Erklärung bitte.

 

[Heyoka955]

Was für ein j und was für eine doppelte for-Schleife? Deine Aussage macht keinen Sinn.

Gut, damit kann man leben Jetzt musst Du nur noch herausfinden, ob die erste Zahl diejenige ist, die sich ständig wiederholt (dann kannst Du Deinen Algorithmus anwenden) oder ob die erste Zahl die gesuchte Zahl ist (dann hättest Du die Zahl sofort gefunden).

Wie viele Zahlen aus der Liste benötigst Du, um mit Sicherheit sagen zu können, ob die erste Zahl die gesuchte ist oder nicht? Mit Erklärung bitte.

ganu einfach bevor ich meinen Algorithmus anwende, gehe ich alles durch ich mache einen markierter und gehe an der ersten Position durch.
Wenn die erste Stelle gleich der zweiten Stelle ist dann erhöhe ich den markierter um 1 und wenn die erste Stelle mit der dritten gleich ist erhöhe ich wieder um 1 und nachdem diese Bedingung fertig ist mache ich eine if abfeage ob Cöunt höher als 1 ist und wenn er höher ist dann weiß ich es komtm mehrmals vor und wenn nicht dann weiß ich die erste Stelle ist meine eine Ziffer die unique ist.

 

[mihe7]

Das funktioniert zwar, ist aber viel zu kompliziert. Es stimmt, Du brauchst die ersten drei Zahlen aus der Liste, denn die gesuchte Zahl kann nur einmal vorkommen, so dass immer mindestens zwei gleiche Zahlen in einer Dreiergruppe vorhanden sein müssen. Wenn die erste Zahl gleich der zweiten ist oder (OR) die erste Zahl gleich der dritten ist, dann (und zwar genau dann) ist die erste Zahl nicht die gesuchte.

Jetzt solltest Du einen Plan haben. Schreib doch mal einen Algorithmus auf, diesmal aber nicht als Beschreibung sondern eine Art Pseudo-Code (braucht/soll kein Java-Code sein).

 

[Blender3D]

Die am besten ("best practice" und "clever") bewertete Lösung:

///...
Arrays.sort(arr);
// ...

Ein Sortierverfahren hat durchschnittlich eine Laufzeit von O(n*log(n)).
Da das Array aus gleichen Nummern bis auf eine besteht, ist die "best practice" hier das Array einmal zu druchlaufen --> Laufzeit von O(n/2).