# Array; Vorkommen zählen



## Jefferio (3. Feb 2013)

Bsp:
int []ar={1,1,2,1,1,18,3,3,9,3}

Die Zahl:
1 ist 4x vorgekommen
2 ist 1x vorgekommen
18 ist 1x vorgekommen
3 ist 3x vorgekommen
9 ist 1x vorgekommen

Mein Programm lautet so: (es gibt auch noch die Häufigste Zahl aus)

```
int []ar={1,1,2,1,1,18,3,3,9,3};
        int counter=1;
        int max=0;
        int maxNumber=0;
        int i;
        int j;  
        
        for(i=0;i<ar.length;i++){
            
            for (j=1;j<ar.length;j++){
                
       
                
                    if (ar[i]==ar[j]){
                     counter++;
                    }
                    if (max<counter){
                        max=counter;
                        maxNumber=ar[i];
                 }
       
            }
           
            System.out.print (ar[i]+": \t"+ counter);
            System.out.println();
            
            counter=0;
            
        } 
        System.out.println ("Häufigste Zahl: "+maxNumber+" kommt "+max+"x vor.");
                
    }
}
```

Leider gibt er mir die 1 zb auch 4x aus, sprich:
_1: 	4
1: 	4
2: 	1
1: 	4
1: 	4
18: 	1
3: 	3
3: 	3
9: 	1
3: 	3
Häufigste Zahl: 1 kommt 4x vor._

Wie mache ich das, das er mir die Zahlen nur 1x ausgibt?


----------



## cklisch (3. Feb 2013)

Ich hab etwas ähnliches wie folgt gelöst:


 Zählarray z mit Größe X erzeugt und alle mit 0 initialisiert.
 Schleife durch das ar-array.
 Hochzählen der Einzelzahlen im Zählarray z[ar_]++;
_
_

Nun stehen in Array z an der jeweiligen Indexposition die Anzahl der Zahlen aus Array ar.

In deinem Beispiel müsste dann etwa rauskommen:

ar[0] = 0;
ar[1] = 4;
ar[2] = 1;
...
_


----------



## xehpuk (3. Feb 2013)

Ein klassischer Fall für eine [JAPI]Map[/JAPI]:


```
static void count(int[] ar) {
	if (ar.length > 0) {
		Map<Integer, Integer> cs = new HashMap<>(ar.length, 1);
		for (int i : ar) {
			cs.put(i, (cs.containsKey(i) ? cs.get(i) : 0) + 1);
		}
		int maxI = 0, maxC = 0;
		System.out.println("Die Zahl:");
		for (int i : cs.keySet()) {
			int c = cs.get(i);
			if (c > maxC) {
				maxI = i;
				maxC = c;
			}
			System.out.printf("%d ist %dx vorgekommen%n", i, c);
		}
		System.out.printf("Häufigste Zahl: %d kommt %dx vor.%n", maxI, maxC);
	}
}
```
Die Lösung des VP stellt gewisse Ansprüche an die übergebenen Zahlen (nicht negativ und nicht zu groß).


----------



## hüteüberhüte (3. Feb 2013)

xehpuk hat gesagt.:


> Ein klassischer Fall für eine [JAPI]Map[/JAPI]:



Overkill, Counting sort reicht auch:


```
public static void main(String[] args) {
        int[] a = {1, 1, 2, 1, 1, 18, 3, 3, 9, 3};
        int[] b = new int[19];

        for (int i : a) {
            b[i]++;
        }

        for (int i = 0; i < b.length; i++) {
            for (int j = 0; j < b[i]; j++) {
                System.out.print(i + ", ");
            }
        }
    }
```



Spoiler: Ausgabe





```
run:
1, 1, 1, 1, 2, 3, 3, 3, 9, 18, ERSTELLEN ERFOLGREICH (Gesamtzeit: 0 Minuten 0 Sekunden)
```


----------



## xehpuk (4. Feb 2013)

hüteüberhüte hat gesagt.:


> Overkill, Counting sort reicht auch:


Du gehst vom immer gleichen Array aus? Overkill, Direktausgabe reicht auch:

```
static void count() {
	System.out.println("Die Zahl:")
	System.out.println("1 ist 4x vorgekommen")
	System.out.println("2 ist 1x vorgekommen")
	System.out.println("3 ist 3x vorgekommen")
	System.out.println("18 ist 1x vorgekommen")
	System.out.println("9 ist 1x vorgekommen")
	System.out.println("Häufigste Zahl: 1 kommt 4x vor.")
}
```
Ausgabe:

```
Die Zahl:
1 ist 4x vorgekommen
2 ist 1x vorgekommen
3 ist 3x vorgekommen
18 ist 1x vorgekommen
9 ist 1x vorgekommen
Häufigste Zahl: 1 kommt 4x vor.
```
Am besten liest du den letzten Satz meines vorigen Beitrags und das allererste Wort des TEs (nochmal).


----------



## hüteüberhüte (4. Feb 2013)

xehpuk hat gesagt.:


> Die Lösung des VP stellt gewisse Ansprüche an die übergebenen Zahlen (nicht negativ und nicht zu groß).



Nicht unbedingt, es kann z.B. auch mit negativen Zahlen umgegangen werden:


```
/**
     * Aufpassen: java.lang.NegativeArraySizeException
     * und java.lang.OutOfMemoryError möglich.
     *
     * @param a Array, welches sortiert werden soll
     * @return neues, sortiertes Array <tt>a</tt>
     */
    public static int[] cs(int[] a) {
        int from = Integer.MAX_VALUE;
        int to = Integer.MIN_VALUE;
        for (int i : a) {
            if (i < from) {
                from = i;
            } else if (i > to) {
                to = i;
            }
        }

        int[] c = new int[to - from + 1];
        int toAdd = -from;
        for (int i : a) {
            c[i + toAdd]++;
        }

        int[] result = new int[a.length];
        for (int i = 0, index = 0; i < c.length; i++) {
            for (int j = 0; j < c[i]; j++) {
                result[index++] = i - toAdd;
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int[] a = {1, 1, 2, 1, 1, 18, 3, 3, 9, 3, -2};
        System.out.println(Arrays.toString(cs(a)));
    }
```

lg LIIII


----------



## hüteüberhüte (4. Feb 2013)

Leeren Arrays handlet die Methode auch, für 1 Element Arrays, einfach folgendes ändern:


```
if (i < from) {
                from = i;
            }
            if (i > to) {
                to = i;
            }
```

Ich habe den gesamten Thread gelesen, mein Problem ist für beschriebene Probleme naheliegend. Du könntest lieber etwas freundlicher sein. Vielen Dank.


----------



## Marco13 (4. Feb 2013)

Dann ist es jetzt: "Nicht zu unterschiedlich"  Die Map ist vermutlich das, was gemeint war, obwohl es eine nette Denksportaufgabe sein könnte, sich zu überlegen, wie die Leute das in C gelöst hätten, ohne Map & Co :reflect: ("Wir hatten ja nix, damals... "  )


----------



## pro2 (4. Feb 2013)

@hüteüberhüte

Deine Lösung verbrät einfach zu viel Speicherplatz, was sie nicht gerade gut macht. Und wenn gewisse Zahlen im Array drinstecken, dann funktioniert deine Lösung schon nicht mehr. Nur mal angenommen, wir hätten -1 Milliarde als Zahl und +1,5 Millarden, dann würde sie versuchen, ein Array von 2,5 Milliarden Elementen anzulegen (nein, eigentlich von irgendeiner negativen Zahl), was schon mal gar nicht klappt und außerdem fast 10 GB Speicher bräuchte, wo soll es den denn hernehmen? Oder versuche mal, das bei einem Array mit long Zahlen zu machen.


----------



## hüteüberhüte (4. Feb 2013)

@pro2: Es ist z.B. auch so etwas möglich:


```
/**
     * Aufpassen: java.lang.NegativeArraySizeException
     * und java.lang.OutOfMemoryError möglich.
     *
     * @param a Array, welches sortiert werden soll
     * @return neues, sortiertes Array <tt>a</tt>
     */
    public static int[] cs(int[] a) {
        int from = Integer.MAX_VALUE;
        int to = Integer.MIN_VALUE;
        for (int i : a) {
            if (i < from) {
                from = i;
            }
            if (i > to) {
                to = i;
            }
        }

        int[] c = new int[to - from + 1];
        int toAdd = -from;
        for (int i : a) {
            c[i + toAdd]++;
        }

        int[] result = new int[a.length];
        for (int i = 0, index = 0; i < c.length; i++) {
            for (int j = 0; j < c[i]; j++) {
                result[index++] = i - toAdd;
            }
        }

        return result;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(cs(new int[]{999, 1, 1, 2, 1, 1, 18, 3, 3, 9, 3, -999})));
        System.out.println(Arrays.toString(cs(new int[]{})));
        System.out.println(Arrays.toString(cs(new int[]{Integer.MIN_VALUE})));
        System.out.println(Arrays.toString(cs(new int[]{Integer.MAX_VALUE})));
        System.out.println(Arrays.toString(cs(new int[]{Integer.MIN_VALUE + 100, Integer.MIN_VALUE})));
        System.out.println(Arrays.toString(cs(new int[]{Integer.MAX_VALUE, Integer.MAX_VALUE - 100})));
    }
```

Natürlich besteht ein Problem, wenn 
	
	
	
	





```
to - from + 1
```
 negativ oder zu groß ist, denn dann wird zu viel Platz verbraten.

ABER: (zu meiner Verteidigung  ) es war von 
	
	
	
	





```
{1,1,2,1,1,18,3,3,9,3}
```
 geredet, und für kleine Bereiche und oft mehrfach auftretende Zahlen ist die Methode einfach super (weil in O(n)  ). lg


----------



## xehpuk (4. Feb 2013)

hüteüberhüte hat gesagt.:


> Ich habe den gesamten Thread gelesen, mein Problem ist für beschriebene Probleme naheliegend.


Ich wollte dir nicht zu nahe treten, aber deine Lösung sollte ja meine "verbessern". Dabei war deine auch nichts anderes als die Umsetzung des Vorschlags meines Vorposters.
Meines Erachtens ist deine Lösung eben nicht naheliegend, da überhaupt nicht hervorgeht, woher die Zahlen in dem Array kommen, woraus sich folglich auch nicht deren Wertebereich erschließen lässt. Der TE hatte lediglich ein Beispiel genannt. Du hast es dir daher mit 
	
	
	
	





```
new int[19]
```
 sehr leicht gemacht. Aber gerade die Variabilität dieser Größe ist der Knackpunkt.
Nach deinem Update für negative Zahlen ist mein Code auch deutlich kürzer als deiner. Außerdem erforderte meiner weniger Hirnschmalz.


----------

