modus stochastics

ocsme

Top Contributor
Guten Tag,
ich wollte nur ein kleines Programm schreiben um die Anzahl von vorkommenden Zahlen in einem Array zu zählen.
Mein erster Ansatz war mit einem Counter doch da kam ich nicht weiter da ich das Problem hatte zu erkennen wann eine neue Zahl kommt! Vielleicht kann das ja jemand noch verbessern :) würde mich freuen.
Hier der Code:
Java:
int[] tmp= {2,2,3,3,3,3,4,4,4,5,8};//mit vargs wie length ermitteln kommt immer nur 1 raus!
   int[] mode=new int[tmp.length+1];
   int counter=0;
   
   for(int i=0;i<tmp.length;i++) {
       int k=mode[tmp[i]];
       if(mode[tmp[i]]==k) {
           counter++;
           mode[tmp[i]]=counter;
       }
       else counter=0;
   }
Dann habe ich mich erinnert das ich letztes Jahr sowas hatte in Alda und ich damit nichts anfangen konnte:
Code:
array b[1...N]
for(i=0;i<A.length){
b[A[i]]++
}
Und so läuft es auch total einfach ;)

Java:
int[] tmp= {2,2,3,3,3,3,4,4,4,5,8};//mit vargs wie length ermitteln kommt immer nur 1 raus!
    int[] mode=new int[tmp.length+1];
   
    for(int i=0;i<tmp.length;i++)    
        mode[tmp[i]]++;
       
    for(int i=0;i<mode.length;i++) {
        System.out.println(i+" "+mode[i]+" ");

Meine nächste frage steht im Kommentar denn ich wollte das ganze in eine Methode packen und nicht immer ein Array vorher erstellen sondern bei der Methode einfach int... args z. B. machen und dann die Argumente mit angeben. Doch wenn ich dann int n=args.length mache kommt immer 1 raus wieso?

LG
 

httpdigest

Top Contributor
Schau dir nochmal diese if-Anweisung an:
Java:
int k = mode[tmp[i]];
if (mode[tmp[i]] == k) {
Fällt dir da was auf?
Damit's klarer wird, was ich meine, schreibe ich die mal so (nur zu Demonstrationszwecken):
Java:
int k = a;
if (a == k) {
Du setzt eine Variable auf einen Wert und prüfst gleich anschließend, ob du die Variable auf den Wert gesetzt hast?
 

MoxxiManagarm

Top Contributor
Meine nächste frage steht im Kommentar denn ich wollte das ganze in eine Methode packen und nicht immer ein Array vorher erstellen sondern bei der Methode einfach int... args z. B. machen und dann die Argumente mit angeben.

Meinst du sowas
Java:
package org.javaforum.examples;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;


public class LimitedNumberCounter {

  public static Map<Integer, Integer> countNumbers(Set<Integer> numbersToCount, int... numbers) {
    Map<Integer, Integer> map = new HashMap<>();
  
    for(Integer numberToCount : numbersToCount) {
      map.put(numberToCount, 0);
    }
  
    for(Integer number : numbers) {
      Integer currentCount = map.get(number);
      if(currentCount != null) {
        map.put(number, ++currentCount);
      }
    }
  
    return map;
  }
 
  public static void main(String[] args) {
    int[] numbers = {2,2,3,3,3,3,4,4,4,5,8};
    Set<Integer> numbersToCount = new HashSet<>(Arrays.asList(2, 4, 8));
  
    Map<Integer, Integer> result = countNumbers(numbersToCount, numbers);
  
    result.forEach((key, value) -> System.out.println(key + ": " + value + " mal"));
  }
}

prints
Code:
2: 2 mal
4: 3 mal
8: 1 mal

Die anderen Zahlen (z.B. 3) werden ignoriert.
 

httpdigest

Top Contributor
Java:
  public static Map<Integer, Integer> countNumbers(Set<Integer> numbersToCount, int... numbers) {
    Map<Integer, Integer> map = new HashMap<>();
 
    for(Integer numberToCount : numbersToCount) {
      map.put(numberToCount, 0);
    }
 
    for(Integer number : numbers) {
      Integer currentCount = map.get(number);
      if(currentCount != null) {
        map.put(number, ++currentCount);
      }
    }
 
    return map;
  }
Bei solchen Aufgaben kribbelt's mir immer in den Fingern, das mit Streams zu machen :)
Java:
import static java.util.function.Function.identity;
import static java.util.stream.Collectors.counting;
import static java.util.stream.Collectors.groupingBy;
import static java.util.stream.IntStream.of;
import java.util.Set;
import java.util.Map;
...
public static Map<Integer, Long> countNumbers(Set<Integer> numbersToCount, int... numbers) {
  return of(numbers)
        .boxed()
        .filter(numbersToCount::contains)
        .collect(groupingBy(identity(), counting()));
}
 

ocsme

Top Contributor
Erstmal wieder super Lieben Dank für die schnelle und tollen Antworten.
Soviel haben wir leider noch nicht gemacht das ich die zwei Programme von euch verstehen kann :-( tut mir leid! Oben mein Code macht es ja auch doch ich wollte es ja mit einem Counter machen auch wenn man Ihn nicht bräuchte KLAR :D
Doch leider hab ich das Problem mit dem Counter auf 0 Setzen deswegen der Ansatz mit dem sinnlosen if(a==k) das ist total sinnlos da kann ich auch gleich einfach i nehmen und er saust genauso durch und gibt mir die selben Zahlen aus :p

Ich mach mir nochmal gedanken vielleicht komme ich ja noch drauf :) sollte doch eigentlich nicht so schwer sein :D
Durchs array laufen und zählen wie oft der Inhalt vor kommt. Mein Problem ist eben abzubrechen wann kommt eine neue Zahl! Da hab ich gerade ein Gedanken fehler :D

Nochmals Super Lieben Dank :) Ihr seit echt KLASSE =)

LG
 

ocsme

Top Contributor
So geht es mit einem Counter und ich muss echt sagen es ist nicht schön :(

Java:
int[] tmp= {1,1,1,1,1,
            2,2,3,3,3,3,3,
            4,4,4,4,4,5,5,6};//mit vargs wie length ermitteln kommt immer nur 1 raus!
   
    int[] a = new int[tmp.length+1];
   
    int counter=0;
    int derzeit=tmp[0];
   
    for(int i=0;i<tmp.length;i++) {
        if(tmp[i]==derzeit) {
            counter++;
            a[derzeit]=counter;
        }
        else {
            counter=1;
            derzeit=tmp[i];
            a[derzeit]=counter;
        }
        derzeit=tmp[i];

       
    }
   
    for(int i=0;i<a.length;i++) {
        System.out.println(i+" "+a[i]);
    }

Da ist das von oben definitiv besser :D

Java:
for(int i=0;i<tmp.length;i++)   
        mode[tmp[i]]++;

2 Zeiler :p
 

MoxxiManagarm

Top Contributor
int[] a = new int[tmp.length+1];

Du wirst mit dem Ansatz immer ein zu großes Array haben. Stell dir vor du hast ein Array aus 1000 1en. Dann hast du ein 1001 langes a in welchem du immer nur das 2. Element hochzählst und an allen anderen Stellen 0 hast. Falls sichergestellt ist, dass nur einstellige Zahlen im Array enthalten sind, dann nimm noch

Java:
int[] a = new int[10];
 

ocsme

Top Contributor
Danke :)
Das ist mir bewusst es ging ja darum das man nicht weiß welche Zahlen im Array stehen ;) Natürlich könnte man dann erstmal das maximum ermitteln und bis dorthin ein array erstellen kann man alles machen klaro =) doch ich wollte ja nur mal so bisjen üben :) und es hat ja beides geklappt :)
Die Antworten von euch habe ich mir angeschaut auch die sachen die ich noch nicht "verstehe". So ein bisschen habe ich das verstanden :) Danke nochmals für eure netten Antworten :)

LG
 

mihe7

Top Contributor
Da ist das von oben definitiv besser
Klar, Du hast die Sache mit dem Counter auch nur halbherzig umgesetzt. In beiden Fällen verfolgst Du den gleichen Ansatz, bei dem die zu zählende Zahl den Array-Index darstellt. Die Counter-Variable ist dabei nur Kosmetik, die verschleiert, was eigentlich passiert.

Beide Ansätze haben eine lineare Laufzeit, weil sie auch funktionieren, wenn das Array nicht funktioniert (EDIT: was schreibe ich da?!? Ich meinte, nicht sortiert ist). Erkauft wird dies durch einen Speicherbedarf in Höhe der größten im Array befindlichen Zahl.

Die Frage ist, ob es möglich ist, den Speicherbedarf zu drücken. Das theoretische Minimum wächst genau so schnell wie die Anzahl verschiedener Zahlen im Array. Es ist mit einem Counter möglich, dieses Minimum zu erreichen, dafür muss das Array allerdings sortiert sein, was die Laufzeit auf O(n log n) erhöht.

Du kannst ja mal ein wenig überlegen :)
 

ocsme

Top Contributor
mihe7, könnte ich nicht einmal durch das Array laufen und mir das maximum raus suchen. Danach ist das zu befühlenden Array ja kleiner. Doch ich denke das meinst du nicht das würde zwar den Speicherplatz in einigen (fast allen) Fällen Minimieren doch das ändert nichts an der Komplexität des Algorithmus ganz im gegenteil ich muss ja mindestens "fast" zweimal durchlaufen. Wenn es ganz schlecht läuft laufe ich ja auch 2 x durch. Wenn angenommen wird das jede Zahl max 1x vorkommt!

Das ganze mit dem Counter ist sehr Halbherzig gelöst da gebe ich dir recht.
Das einzige was mir da einfällt ist eben wie gesagt sowas hier:

Java:
int[] tmp= {1,1,1,1,1,2,2,3,3,3,3,3,4,4,4,4,4,5,5,6};
   
    int anzahl=0;
    for(int i=0;i<tmp.length;i++)
        if(tmp[i]>anzahl)
            anzahl=tmp[i];
   
    int[] a = new int[anzahl+1];
   
    for(int i=0;i<tmp.length;i++)
        a[tmp[i]]++;
   
   
    for(int i=0;i<a.length;i++)
        System.out.println(i+" "+a[i]);

Ausgabe ist:
0 0
1 5
2 2
3 5
4 5
5 2
6 1

Jetzt fehlt nur noch die 0 Zu löschen dann hätten wir doch relativ gut das Problem gelöst.

Kann mir vielleicht noch jemand etwas sagen zu dem Problem mit dem vargs?
Denn ich habe das Problem wenn ich das bei einer Methode mit gebe dann kommt bei int... args z. B. args.length immer 1 raus :( obwohl ich 10 Elemente mehr oder weniger anhänge.

LG
 

ocsme

Top Contributor
Ausgabe ohne die 0 meinte ich oben nicht das geht ja ganz einfach sondern das sie gar nicht gespeichert wird!
Java:
for(int i=1;i<a.length;i++) {
        System.out.println(i+" "+a[i]);
    }

Ausgabe:
1 5
2 2
3 5
4 5
5 2
6 1

SO NICHT!
 

mihe7

Top Contributor
könnte ich nicht einmal durch das Array laufen und mir das maximum raus suchen. Danach ist das zu befühlenden Array ja kleiner.
Bei Deinem Ansatz könntest Du das nicht nur machen, sondern Du musst es so machen, wenn er für den allgemeinen Fall funktionieren soll. Wenn Du in Dein Array eine Zahl 100 einfügst, musst Du ein Array der Größe 101 anlegen, selbst wenn die 100 die einzige Zahl in Deinem Array wäre.

Doch ich denke das meinst du nicht
Richtig. Stehen im Eingabe-Array m verschiedene(!) Zahlen, dann soll der Speicherbedarf linear zu m sein.

ändert nichts an der Komplexität des Algorithmus ganz im gegenteil ich muss ja mindestens "fast" zweimal durchlaufen.
Das würde bzgl. der Laufzeitkomplexität keine Rolle spielen, die bliebe linear zur Anzahl der Elemente.

Das einzige was mir da einfällt ist eben wie gesagt sowas hier:
OK, ein Tipp:
Code:
Eingabe: 1,1,1,1,2,2,2,100
Zahlen: 1, 2, 100
Anzahl: 4, 3, 1

Kann mir vielleicht noch jemand etwas sagen zu dem Problem mit dem vargs?

Java:
public class Test {
    public void test(int ... args) {
        System.out.println(args.length);
    }

    public static void main(String[] args) {
        new Test().test(1,2,3);
    }
}
 

MoxxiManagarm

Top Contributor
Wenn das zu zählende immer Array sortiert ist, dann brauchst du ja nicht mal einen Speicher. Dann kannst du immer den Zähler ausgeben, sobald du eine neue Zahl oder das Ende des Arrays gefunden hast.

Java:
int[] numbers = {1, 1, 1, 1, 1, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 6};

    int currentCounter = 0;
    int currentNumber = 0;

    for (int number : numbers) {
      if(number == currentNumber) {
        currentCounter++;
      } else {
        if(currentCounter != 0) {
          System.out.println(currentNumber + " occured " + currentCounter + " times.");
        }
       
        currentNumber = number;
        currentCounter = 1;
      }
    }
   
    System.out.println(currentNumber + " occured " + currentCounter + " times.");
 

ocsme

Top Contributor
mihe7 Danke für die antwort :)
Das mit dem varags klappt jetzt ich hab da irgendwo wohl mal wieder ein Fehler gemacht. Leider hab ich den Code nicht mehr hab es gestern gelöscht :( Hab mir schon gedacht das dort etwas nicht stimmen kann :D Danke :)

Der Code von die Moxxi ist vermutlich auch das was mihe7 gemeint hat :)
Vor allem läuft man ja jetzt auch nur 1x durch das Array. Ich bräuchte ja definitiv immer mehr Durchläufe. Wenn man dann noch den ArbeitsspeicherPlatz dazu nimmt ist meine Variante höchst ineffektiv :D
Selbst wenn man es nur schafft in einem Array wie z. B. hier: 1,1,1,2,2,2,100 nur die 3 Zahlen 1,2 und 100 zu kopieren und diese dann zählt müsste man doch zwei mal durch das array 1,1,1,2,2,2,100 durchlaufen oder etwa nicht? Wenn ich falsch liege dann bitte ich um Verbesserung mir fällt doch nichts anderes mehr ein :)

Denke damit haben wir das ganze doch sehr gut gelöst bekommen bzw. ihr :)

LG
 

httpdigest

Top Contributor
Wenn man dann noch den ArbeitsspeicherPlatz dazu nimmt ist meine Variante höchst ineffektiv
Deine Methode wäre genauso effektiv wie alle bisher vorgeschlagenen. Selbst, wenn deine Methode darin bestünde, alle Computer der Welt miteinander zu vernetzen, um die Anzahl der Zahlen zu bestimmen, wäre das genauso effektiv, denn du erreichst damit ja denselben Effekt, nämlich, dass am Ende die Anzahl der Zahlen ausgegeben wird. Es wäre nur nicht besonders effizient.
 

mihe7

Top Contributor
Der Code von die Moxxi ist vermutlich auch das was mihe7 gemeint hat
Nein, das wollte ich Dir erst unter die Nase reiben, wenn Du es mit Arrays gelöst hättest :p

Hintergrund ist: wenn Du die Anforderungen ein klein wenig änderst, funktioniert das mit der direkten Ausgaben nicht mehr.

und diese dann zählt müsste man doch zwei mal durch das array 1,1,1,2,2,2,100 durchlaufen oder etwa nicht?
Ja, man erkauft sich den geringeren Speicherbedarf durch eine höhere Laufzeit und oft funktioniert es auch umgekehrt.

Zum Beispiel könnte man beide Ausgabe-Arrays jeweils genauso groß wie das Eingabe-Array machen (man nimmt also erst einmal an, dass alle Zahlen im Eingabe-Array unterschiedlich sind) und einen Zähler hinzunehmen. Letzterer zählt mit, wie viele unterschiedliche Elemente tatsächlich in das Array geschrieben wurden. Damit kannst Du Dir wieder einen Array-Durchlauf sparen. Bzgl. der Laufzeitkomplexität ändert sich dadurch aber nichts.

Mal etwas ausführlicher:
Java:
public class Test {

    public static void main(String[] args) {
        Test.count(1,1,1,2,2,2,100,100);
    }

    static void count(int ... args) {
        java.util.Arrays.sort(args); // LK in O(n log n)

        int distinctValues = distinct(args);  // LK in O(n)
        int[] values = new int[distinctValues]; // PK in O(m) mit m <= n
        int[] counts = new int[distinctValues]; // PK in O(m) mit m <= n

        count(values, counts, args);   // LK in O(n)
        for (int i = 0; i < distinctValues; i++) { // LK in O(m) mit m <= n
            System.out.printf("%d: %d mal\n", values[i], counts[i]);
        }
        // Laufzeitkomplexität (LK) gesamt: O(n log n) 
        // Platzkomplexität (PK) gesamt: O(m)
     }

    static int distinct(int[] args) {
        int count = 0;
        int last = 0;
        for (int value : args) {
            if (count == 0 || last != value) {
                last = value;
                count++;
            }
        }
        return count;
    }

    static void count(int[] values, int[] counts, int[] args) {
        int ix = -1;
        for (int value : args) {
            if (ix == -1 || values[ix] != value) {
                ix++;
                values[ix] = value;
                counts[ix] = 1;
            } else {
                counts[ix]++;
            }
        }
    }
}
Statt distinct() aufzurufen könnte man eben auch einfach distinctValues auf arr.length setzen. Dann muss man beim eigentlichen Zählen aber die tatsächliche Anzahl der Zahlen im Ausgabe-Array zurückgeben oder man verwendet einen Wert, der das "End of Array" markiert. Das muss natürlich ein Wert sein, der in der Eingabe nicht vorkommen kann.
 

Ähnliche Java Themen

Neue Themen


Oben