Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

KillSingles

Werbeanzeige

Sk!p

Alter Hase

  • »Sk!p« ist der Autor dieses Themas

Beiträge: 568

  • Private Nachricht senden

1

29.06.2007, 19:25

KillSingles

hi,

ich hänge hier gerade an einer kleinen Programmieraufgabe, die ich irgendwie nicht implementiert bekomme. Das Ganze soll in java stattfinden, was allerdings auf dem Gebiet zu cpp kaum einen Unterschied macht ;)

Es sollen aus einem übergebenen Array alle Einträge entfernt werden, die nur einmal vorkommen, die Reihenfolge soll beibehalten werden. Collections und Rekursion dürfen nicht benutzt werden.

Ich hatte jetzt zwei ideen, die allerdings beide daran scheitern, dass ich die Größe des Ergebnisarray ja schon beim erstellen wissen muss:

1) Ich erstelle ein bool-Array mit der gleichen größe wie das übergebene und setze dann immer auf true/false, wenn der Eintrag doppelt gefunden wurde. Allerdings weiß ich dann ja nie, welche Einträge ich schon gefunden hab, da ja nur true/false gespeichert wird.

2) Ich betrachte immer nur jeweils einen Eintrag und durchsuche das Restarray auf den gleichen Eintrag. Nur wenn ich diesen dann nochmal finde, kann ich ihn ja wieder nirgendwo vernünftig speichern, weil ich keinen Stack oä. hab. Mal abgesehen davon, dass die Laufzeit auch beschissen is :D

Ideen? :)

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

2

29.06.2007, 19:35

Sehe ich das richtig:
Eingabe = Array
Ausgabe = neues Array, wo alle einzelnen Einträge weg sind

Wo ist dann das Problem?
Mach doch das Rückgabe-Array erstmal so groß wie das Original-Array. Dann füllst du es. Wenn du fertig bist, weißt du, wie viel Platz du wirklich brauchst und machst ein neues Array mit dieser Größe, in welches du das Ergebnis reinkopierst.
David Scherfgens Website | Konzentrationstest Polizei

Sk!p

Alter Hase

  • »Sk!p« ist der Autor dieses Themas

Beiträge: 568

  • Private Nachricht senden

3

29.06.2007, 20:45

Das hab ich auch schon probiert, aber das Problem ist, dass bei java alle Einträge, die nicht benutzt automatisch initialisiert werden. Im Falle von int ist das dann 0. Und wenn ich das Array so zurückgebe, dass hinten noch 0en dranhängen, schlägt das Testsystem fehl und wenn ich jetzt zb folgendes Eingabearray hab:

1 2 3 0 0 dann kommt bei dem Zwischenarray das raus:
0 0 0 0 0 und da weiß ich dann ja nicht, ob er die Null doppelt gefunden hat oder gar nix.

dot

Supermoderator

Beiträge: 9 757

Wohnort: Graz

  • Private Nachricht senden

4

29.06.2007, 20:55

Zitat von »"David Scherfgen"«

weißt du, wie viel Platz du wirklich brauchst und machst ein neues Array mit dieser Größe, in welches du das Ergebnis reinkopierst.


...
m4studios

grek40

Alter Hase

Beiträge: 1 491

Wohnort: Dresden

  • Private Nachricht senden

5

29.06.2007, 20:56

Gibt es denn keinen Wert der garantiert nicht vorkommt, und der damit zur initialisierung geeignet ist?

Nox

Supermoderator

Beiträge: 5 272

Beruf: Student

  • Private Nachricht senden

6

29.06.2007, 21:06

Quellcode

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

ArbeitsArray = new bool[GrößeDesEingabeArrays]
for(int x = 0; x < GrößeDesEingabeArrays; x++)
{
      for(int y = x + 1; y < GrößeDesEingabeArrays; y++)
      {
              if(EingabeArray[x] == EingabeArray[y])
              {
                     ArbeitsArray[x] = true
                     ArbeitsArray[y] = true
              }
      }
}

int counter = 0;
foreach Element of ArbeitsArray 
      if(ArbeitsArray == true)
               counter++;

AusgabeArray = new int[counter]

int x = 0
int counter = 0
foreach Element of ArbeitsArray 
{
      if(ArbeitsArray == true)
      {
            AusgabeArray[counter] = EingabeArray[x]
             counter++
      }
      x++
}


dürfte doch gehen oder? Die Aufwandsordnung( T(n² + 2n) ist halt recht dürftig aber was solls.
PRO Lernkurs "Wie benutze ich eine Doku richtig"!
CONTRA lasst mal die anderen machen!
networklibbenc - Netzwerklibs im Vergleich | syncsys - Netzwerk lib (MMO-ready) | Schleichfahrt Remake | Firegalaxy | Sammelsurium rund um FPGA&Co.

Sk!p

Alter Hase

  • »Sk!p« ist der Autor dieses Themas

Beiträge: 568

  • Private Nachricht senden

7

30.06.2007, 13:19

jep, so gehts. Wen es interessiert, hier noch die Musterlösung:

Quellcode

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

01 public static int[] studentsMethod(final int[] array_in) {
02 
03 
int counter = 0;
04 for (int i = 0; i < array_in.length; i++) {
05   int toLookFor = array_in[i];
06   boolean takeIt = false;
07   for (int j = 0; j < array_in.length; j++)
08     if (toLookFor == array_in[j] && i != j)
09       takeIt = true;
10   if (takeIt)
11     counter++;
12 }
13 
14 int[] result = new int[counter];
15 int pointer = 0;
16 
17 for (int i = 0; i < array_in.length; i++) {
18   int toLookFor = array_in[i];
19   boolean takeIt = false;
20   for (int j = 0; j < array_in.length; j++)
21     if (toLookFor == array_in[j] && i != j)
22       takeIt = true;
23   if (takeIt) {
24     result[pointer] = toLookFor;
25     pointer++;
26   }
27 }

28     
29 return result;
30 }

Werbeanzeige