Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Praktische Informatik (http://www.informatikerboard.de/board/board.php?boardid=6)
---- Softwaretechnik (http://www.informatikerboard.de/board/board.php?boardid=18)
----- Implemtierung Algorithmus (http://www.informatikerboard.de/board/thread.php?threadid=2843)


Geschrieben von Der_Fichtenelch am 06.02.2016 um 15:16:

  Implemtierung Algorithmus

Meine Frage:
Hallo zusammen,

folgende Aufgabe:

Gegeben sei eine Folge ganzer Zahlen, deren Werte in dem fest gewählten Bereich {1,?.,N} liegen. Dabei sei n sehr viel größer als N. Es soll ermittelt werden, welche Zahl in der Folge am häufigsten vorkommt. Falls mehrere solche Zahlen existieren, soll eine beliebige davon ausgewählt werden. Finden Sie einen geeigneten Algorithmus zur Lösung des Problems und implementieren Sie diesen in Java. Geben Sie die Komplexität an.

Meine Ideen:
Ehrlich gesagt fehlt mir der Ansatz für eine Lösung.

Vielen Dank für etwailige Ansätze.



Geschrieben von eulerscheZahl am 06.02.2016 um 15:20:

 

Erstelle ein Array der Größe N. Dort speicherst du, welche Zahl (=Index) wie oft (=wert an Index) vorkommt.
Iteriere dann über das Array und erhöhe den passenden Eintrag.



Geschrieben von Der_Fichtenelch am 06.02.2016 um 15:29:

 

Danke für die schnelle Antwort.

Hab hier mal etwas zusammengeschrieben, meintest du das?

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
package übung4_aufgabe1;

public class Übung4_Aufgabe1 
{
    public static void main(String[] args) 
    {
        int [] zahlen = {1,2,3,1,1}; 
        int N = 20; 
        int [] array = new int [N];
        
        for (int i=0;i<array.length;i++)
        {
            switch (zahlen[i])
            {
                case 1: 
                    array[0]+=1;
                    break; 
                //Hier folgen noch weitere Cases; 
            }
        }
    }
}



Geschrieben von eulerscheZahl am 06.02.2016 um 15:32:

 

Im Prinzip ja, aber nicht mit switch-case.
Eher so: array[zahlen[i]]++;

Und natürlich musst du bis zahlen.length gehen, nicht array.length



Geschrieben von Der_Fichtenelch am 06.02.2016 um 15:38:

 

Danke für die Hilfe.


Forensoftware: Burning Board, entwickelt von WoltLab GmbH