[Java] Array Teilmenge eines Arrays ?

Mr. Mouse · 20. Dezember 2011

Array Teilmenge eines Arrays ?

Angenommen ich habe 2 char-Arrays

char[] a = {'a','b','c')
char[] b = {'a','b');

Wie kann ich nun testen, ob das Array b in a enthalten ist bzw ob die elemente von b in a enthalten sind?

Anzeige

harry1526 · 20. Dezember 2011

AW: Array Teilmenge eines Arrays ?

hi,

folgende voraussetzungen müssen gegeben sein. ansonsten funktioniert es nicht.

die arrays müssen sortiert sein!

du machst eine schleife um das array a in dieser schleife nimmst du das aktuelle element und überprüfst diese in dem zweiten array, an der gleichen position

Code:

public class Main {

 static char[] a = { 'a', 'b', 'c' };
 static char[] b = { 'a', 'b' };

 private static boolean checkValues(char currentChar, int position) {
 return currentChar == b[position];
 }

 /**
 * @param args
 */
 public static void main(String[] args) {
 for (int i = 0; i < a.length; i++) {
 if (i < b.length) {
 if (checkValues(a[i], i)) {
 System.err.println("true");
 } else {
 System.err.println("false");
 }
 }
 }
 }
}

DasBoeseLebt · 20. Dezember 2011

AW: Array Teilmenge eines Arrays ?

Spielt die Reihenfolge bzw die Position der Elemente eine Rolle?

Figger · 20. Dezember 2011

AW: Array Teilmenge eines Arrays ?

Code:

Arrays.asList(a).containsAll(Arrays.asList(b));

Mr.y · 20. Dezember 2011

AW: Array Teilmenge eines Arrays ?

wollte ich gerade sagen....arbeite zwar mit c#
aber mit "Contains" sollte man das rausbekommen können

tabasco · 21. Dezember 2011

AW: Array Teilmenge eines Arrays ?

Wenn die Arrays unsortiert sind kannst du auch einfach schritt für schritt prüfen, ob das zeichen an der stelle 0 in array a irgendwo in b vorhanden ist, wenn ja machst du das selbe an der stelle 1,2,3 usw. bis das kleiner array durch ist, wenn nein weisst du ja, dass es nicht vorhanden ist...

Mever · 22. Dezember 2011

AW: Array Teilmenge eines Arrays ?

Hallo! Ich hab mich auch mal an das "Problemchen" gemacht und eine kleine Methode geschrieben. Die Lösungen mit den angebotenen Methoden die von Java gestellt werden sind zwar besser, effizienter, schneller usw. aber wenn man das Problem nachvollziehen will dann ist ein selbst ausgedachter Algo meiner Meinung nach besser (für den Lernerfolg).

Hier hab ich dir den Code (mit Kommentaren natürlich ), ich hoffe er ist verständlich.

Bei diesem Algo ist es egal ob das Array sortiert ist oder nicht!

Code:

public class RaidRush{
 public RaidRush(){
 char[] a = {'a','b','c'};
 char[] b = {'a','b'};

 System.out.println("b ist teilmenge von a: " + pruefeAufTeilmenge(b,a));
 }
 
 public boolean pruefeAufTeilmenge(char[] menge, char[] obermenge){
 //Speichert an jeder Stelle analog ob das Zeichen in der Obermenge enthalten ist
 boolean[] check = new boolean[menge.length];
 
 for(int i = 0; i < menge.length; i++){
 for(int j = 0; j < obermenge.length; j++){
 //Nehme das i-te Element von der Menge und 
 //Vergleiche es mit dem j-ten Element der Obermenge
 if(menge[i] == obermenge[j]){
 check[i] = true; //Ein Element von Menge ist in Teilmenge
 break; //Schleife beenden
 }else{
 check[i] = false;
 }
 }
 }
 
 for(int i = 0; i < check.length; i++){
 //Wenn an einer Stelle false steht, dann ist die Menge auch keine Teilmenge
 if(!check[i]){
 return false; 
 }
 }
 
 return true;
 }
 
 public static void main(String[] args){
 RaidRush r = new RaidRush();
 }

}

Das ist bestimmt nicht die beste Lösung, aber allzu schlecht sollte sich auch nicht sein.

Ps.: Kannst gleich so durch den Kompiler jagen

Gruß Mever :]

bloodyphoenix · 23. Dezember 2011

AW: Array Teilmenge eines Arrays ?

Theoretisch ists bei unsortierten Arrays fast die beste möglichkeit, außer ein paar Kleinigkeiten (hervorgehoben, auch für deinen Lernerfolg =) )

Code:

public class RaidRush{
 public RaidRush(){
 char[] a = {'a','b','c'};
 char[] b = {'a','b'};

 System.out.println("b ist teilmenge von a: " + pruefeAufTeilmenge(b,a));
 }
 
 public boolean pruefeAufTeilmenge(char[] menge, char[] obermenge){
 //Speichert an jeder Stelle analog ob das Zeichen in der Obermenge enthalten ist
 [b]//boolean[] check = new boolean[menge.length];
 boolean check;[/b]

 for(int i = 0; i < menge.length; i++){
 for(int j = 0; j < obermenge.length; j++){
 [b]check=false[/b]
 //Nehme das i-te Element von der Menge und 
 //Vergleiche es mit dem j-ten Element der Obermenge
 if(menge[i] == obermenge[j]){
 [b]//check[i] = true; //Ein Element von Menge ist in Teilmenge
 check = true;[/b]
 break; //Schleife beenden
 [b]}else{
 //check[i] = false;[/b]
 }
 }
 [b]if (!check) return false;[/b]
 }
 
 [b]/*
 for(int i = 0; i < check.length; i++){
 //Wenn an einer Stelle false steht, dann ist die Menge auch keine Teilmenge
 if(!check[i]){
 return false; 
 }
 }
 */[/b]
 return true;
 
 }
 
 public static void main(String[] args){
 RaidRush r = new RaidRush();
 }

}

Spart Speicher für das Array, unnötige Zuweisungen (check = false), unnötige Schleifendurchläufe, falls ein Gegenbeispiel gefunden wurde und die komplette Schleife am Ende. Sind zwar alles konstante Faktoren, aber trotzdem nicht unwichtig^^ (bei 3 elementigen Arrays vielleicht, aber nehmen wir mal 100000 Elementige Arrays)

Nichts destotrotz hat der Algo eine Laufzeit von O(n*m) (also sagen wir mal "quadratisch"). Mit sortierten Arrays geht das in linearer Zeit (O(max(n,m))).
Mir fällt grade auf, dass es somit (jedenfalls theoretisch) schneller gehen dürfte die Arrays (on Demand) mit z.B. MergeSort zu sortieren und danach zu vergleichen, als es "naiv" zu vergleichen, wies der obere Algo tut [2*n*log(n)+n => O(n*logn)<O(n²), oder nicht?]

powernator · 23. Dezember 2011

AW: Array Teilmenge eines Arrays ?

Bin ich einfach nur zu müde, oder macht dein Code, bloodyphoenix, keinen Sinn?

Dadurch, dass check am Anfang der 2. Schleife auf false gesetzt wird, zählt doch im Endeffekt immer nur der Fall

Code:

menge[i]==obermenge[ (obermenge.length - 1) ]

bei deinem Code, oder?

Code:

 for(int i = 0; i < menge.length; i++){
 check = false;
 for(int j = 0; j < obermenge.length; j++){
 if(menge[i] == obermenge[j]){
 check = true;
 break; //Schleife beenden
 }
 }
 if (!check) return false;
 }

Wäre natürlich etwas anderes

Mazen2004 · 23. Dezember 2011

AW: Array Teilmenge eines Arrays ?

Müssen es arrays sein? Ansonsten eignen sich für diese Operationen sets.
Da gibt es extra Methoden genau für sowas, die man einfach nur aufrufen muss.

Mr. Mouse · 23. Dezember 2011

AW: Array Teilmenge eines Arrays ?

habs viel einfacher gelöst

Code:

private static final char[] hex_values = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
private static long convertToDec(String eingabe, int base) {
 long dec = 0;
 hex = eingabe.toCharArray();
 char[] values = Arrays.copyOf(hex_values, base);
 if(hex.length == 8) {
 try {
 for(int i=0; i<hex.length; i++) {
 dec += Integer.parseInt(String.valueOf(hex[i]), base)*Math.pow(base, Math.abs(i-7));
 }
 } catch(Exception nfe) { dec = -1; }
 } else { dec = -1; }
 return dec;
 }
}

Nützliche Suchen

[Java] Array Teilmenge eines Arrays ?

Videos zum Themenbereich