ubuntuusers.de

Hey, ich habe folgendes kleines Problem: Ich möchte in Java ein Programm schreiben, dass einenn 2d-Array erzeugt und diesen nach einen bestimmten Algorithmus befüllt. Der Teil klappt schon mal. Als nächstes will ich mir nur noch die Werte ausgeben lassen, welche doppelt vorkommen. Gibt es da irgendeine Funktion in Java die das ermöglicht und dabei auch noch gewisse Parameter zulassen? Dass beispielsweise nicht die Vertauschung von Summanden (also nicht a+b<>b+a) akzeptiert wird?

Wenns Java nicht kennt, dann machst dus eben selbst. 😉

Ein möglicher Algorithmus wäre für jedes Element alle folgenden Elemente zu überprüfen. Etwas einfacher zu implementieren wäre dann ein Test für die aktuelle und alle weiteren „Zeilen“.

dabei auch noch gewisse Parameter zulassen? Dass beispielsweise nicht die Vertauschung von Summanden (also nicht a+b<>b+a) akzeptiert wird?

Diesen Teil verstehe ich leider nicht ganz.

Grüße, Keba.

VicariousVirus schrieb:

Als nächstes will ich mir nur noch die Werte ausgeben lassen, welche doppelt vorkommen.

Welche Art von Werten sind denn in Deinem Array? DatabaseConnections? JFileChooserDialogs? ints?

Gibt es da irgendeine Funktion in Java die das ermöglicht und dabei auch noch gewisse Parameter zulassen? Dass beispielsweise nicht die Vertauschung von Summanden (also nicht a+b<>b+a) akzeptiert wird?

Was für Summanden? Wieso könnten die denn akzeptiert werden?

Wenn es unbedingt Java sein muss und du viel mit Listen arbeitest empfehle ich:

https://code.google.com/p/lambdaj/wiki/LambdajFeatures

oder

https://code.google.com/p/guava-libraries/

In Java manuell filtern:

1
2
3
4
5
6
7
8

List<Integer> allInts = new ArrayList();
List<Integer> filtered = new ArrayList();

for (Integer i : allInts) {
    if ( i < 42){
        filtered.add(i);
    }
}

Mit dem richtigen Werkzeug (Scala) auf der jvm:

1

List(1,2,3,42,99) filter (_ < 42)

Ich würde empfeheln, HashSet.add() zu benutzen. .add() teilt per Wahrheitswert mit, ob ein neu hinzuzufügender Wert bereits in der Menge vorhanden ist. Dies kann man nutzen, um doppelte Werte zu ermitteln, ohne eine quadratische (und damit üble) Laufzeit zu bekommen. Mal schnell hingepfuscht:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

import java.util.HashSet;
import java.util.Set;

public class Doppelermittler {
    public static void main(String[] args) {
        int[] elems = {1, 5, 2, 1, 3, 2};
        Set<Integer> doppelteElemente = gibDoppelteElemente(elems);
        System.out.println("Folgende Elemente kamen mehrfach vor:");
        System.out.println(doppelteElemente);
    }

    private static Set<Integer> gibDoppelteElemente(int[] elems) {
        Set<Integer> bereitsGesehen = new HashSet<>();
        Set<Integer> doppelte = new HashSet<>();
        for (int elem : elems) {
            if (!bereitsGesehen.add(elem)) {
                doppelte.add(elem);
            }
        }
        return doppelte;
    }
}

Den zweiten Teil deiner Frage ("1 + 2" und "2 + 1" als äquivalent ansehen) kann man evtl ebenfalls mit HashSets lösen. Da bräuchte man aber mehr Details, wie ein solches Element tatsächlich aufgebaut ist.

Alternativ könnte man das Array in eine Liste kopieren, diese sortieren, und dann mit zwei Indizees darüber wandern.

Was ist, wenn Werte 3fach, 4fach, 5fach vorkommen? Ein Wert der 3fach vorkommt kommt je nach Betrachtungsweise nicht (genau) doppelt vor.

ich hätte die Aufgabenstellung lesen sollen ☺

Scala:

1
2
3

val aa =Array(1,2,2,3,3,4)
aa filterNot  (a => aa.count(_ == a) == 1 ) distinct
//res2: Array[Int] = Array(2, 3)

Für die speziellen Wertpaare würde ich case classes nehmen die liefern den Test auf Gleichheit mit.

Scala:

1
2

case class Sum(a:Int,b:Int)
Sum(2,3) != Sum(3,2)

In Java würde ich mir das nicht mehr antun.

user unknown schrieb:

Alternativ könnte man das Array in eine Liste kopieren, diese sortieren, und dann mit zwei Indizees darüber wandern.

Welcher Vorteil daran würde deiner Meinung nach den Mehraufwand für's Sortieren aufwiegen?

user unknown schrieb:

VicariousVirus schrieb:

Als nächstes will ich mir nur noch die Werte ausgeben lassen, welche doppelt vorkommen.

Welche Art von Werten sind denn in Deinem Array? DatabaseConnections? JFileChooserDialogs? ints?

Gibt es da irgendeine Funktion in Java die das ermöglicht und dabei auch noch gewisse Parameter zulassen? Dass beispielsweise nicht die Vertauschung von Summanden (also nicht a+b<>b+a) akzeptiert wird?

Was für Summanden? Wieso könnten die denn akzeptiert werden?

Ich warte immer noch auf die Klärung dieser Fragen und wundere mich ein wenig darüber, dass Ihr schon Lösungen parat habt. Habe ich etwas übersehen? Ist wirklich alles klar?

Ciao

robert

Man kann aus den Angaben durchaus erste Lösungansätze erstellen, finde ich. Ob das bereits ausreicht, um es auf das tatsächliche Problem zu übertragen, bleibt abzuwarten...

snafu1 schrieb:

user unknown schrieb:

Alternativ könnte man das Array in eine Liste kopieren, diese sortieren, und dann mit zwei Indizees darüber wandern.

Welcher Vorteil daran würde deiner Meinung nach den Mehraufwand für's Sortieren aufwiegen?

Nun, wenn ich ein Array, lass es mich aber als Liste darstellen, habe:

1, 2, 3, 1, 2, 4, 1, 4

Ich will wissen, ob das erste Element doppelt, also - ich gehe mangels weiterer Angaben mal davon aus: exact doppelt - vorkommt. Ich schaue es an: eine 1, wandere bis zum vorletzten Element, und weiß nun: ah - zu oft. Nun gehe ich zum 2. Element. Hier muss ich bis zum Ende wanderen, um zu wissen, dass es nicht mehr als 2x vorkommt. So muss ich für viele Elemente bis zum Ende wandern.

1, 1, 1, 2, 2, 3, 4, 4

Hier wandere ich nach dem Sortieren nur 2x durch die gesamte Sammlung, mit einem Index auf das erste erste Element, und einem auf das letzte eines Wertes, also anfangs von Index (0,0) erhöhe ich den höheren bis (0, 2), bei (0, 3) bin ich drüber raus und (3-0) ergibt die Zahl der Elemente. Dann setze ich die Indizees auf (3,3) und wandere mit dem größeren weiter auf der Suche nach el(j) > el(i).

Sortieren ist außerdem als Bibliotheksfunktion verfügbar und hoffentlich fehlerfrei, und Fehlerfreiheit ist einfach immer erwünscht. Von Performance habe ich nichts gelesen.

Ganz unabhängig von "Java" würde ich solche Suchaufgaben mit einem assoziativen Array lösen, bei dem der Zelleninhalt als Index dient, und in dem ggf. der zugehörige Arrayindex des originalen Arrays als Wert hinterlegt ist.

Das erspart einem dann nämlich die Vergleichsoperationen: man braucht nur zu gucken, ob es eine Zelle "$sucharray[zelleninhalt]" schon gibt, und sonst einfach zum aktuellen Zelleinhalt eine neue Arrayzelle anlegen. So ähnlich, wie ich es hier mal gemacht hatte, oder hier.

Der Preis ist, dass man ein entsprechendes Array im Arbeitsspeicher anlegt, aber das dürfte bis zu einer Arraygröße von 10 Mill. Zellen kein Problem sein.

LG,

track

Also es geht erst mal um int bzw long Werte. Welche aus eines Funktion hervorgehen. Nun soll es möglich sein, dass diese als Summe im 2d-Array hinterlegt werden. Der Haken an der Sache ist, dass manche Summe doppelt vorkommen, aber nicht einfach aus der Vertauschung zweier Summanden. Also nicht 1+2 und 2+1 meinetwegen. Es wäre natürlich auch möglich, nach vier gleichen Werten zu suchen. Wichtig ist nur, dass die gleichen Werte ausgeben werden. Daran hadere ich gerade.

user unknown schrieb:

Von Performance habe ich nichts gelesen.

Super... 😀

Naja, ich würde die Liste / das Array / whatever wohl in eine HashMap() packen, dessen Werte ich pro Element entsprechend hochzähle. Die Voraussetzung dafür ist natürlich, dass sie hashbar sind. So ähnlich wie beim Sortieren ja auch vorausgesetzt wird, dass die Objekte sinnvoll miteinander vergleichbar sind. Wir brauchen mehr Infos.... ^^

EDIT: Beitrag wurde verfasst, bevor ich die beiden Postings über mir gesehen habe.

Was steht denn nun in den Zellen ? - sind das Rechenaufgaben á la 1+2 2+1 8-5 ... usw, ? - und: kommt es dabei auf den genauen Aufgabetext an, oder nur auf das Ergebnis ?

Dementsprechend müsste man ja dann den Index für das Sucharray vorbehandeln ...
(Vielleicht zeigst Du mal einfach ein Beispiel, wo man sehen kann was Du genau als "gleich" suchst und was nicht ...?)

track