Geteilte Liste auf eindeutigen Chargen

Question

Wir haben eine Liste von Strings-Elementen. Zum Beispiel [A, B, B, A, K, B]. Unser Programm muss diese Liste auf die nächsten Chargen [["A", "B", "K"], ["B", "A"], ["B"]] aufteilen. Alle Butches müssen nur eindeutige Elemente enthalten, die Anzahl der Batches muss minimal sein und die Komplexität des Algorithmus muss linear O (n) sein.

Answer 1

ich normalerweise nicht beantworten, wenn die Fragen wie ein Hausaufgaben sieht, was ich denke, es ist. Aber gut ... hier ist eine nette und einfache Lösung mit List, Set und . (Wenn Sie über die Reihenfolge egal, ersetzen dann HashSet mit LinkedHashSet)

---

import java.util.*; 

public class StringBatches { 
    public static void main(String[] args) { 
     String[] ss = {"A","B","B","A","K","B", "A"}; 

     List<Set<String>> l = new ArrayList<Set<String>>(); 
     for (String s : ss) { 
      putInUniqueSet(l, 0, s); 
     } 
     System.out.println(l); 
    } 

    public static boolean putInUniqueSet(List<Set<String>> l, int idx, String s) { 
     if(l.size() <= idx) 
      l.add(new HashSet<String>()); 
     return !l.get(idx).add(s) ? putInUniqueSet(l, idx+1, s) : true; 
    } 
} 

---

Ausgang:

[[A, B, K], [A, B], [A, B]] 

Answer 2

Versuchen Sie, die Liste zu verwenden und festzulegen. Ihr Set erlaubt keine doppelten Werte und List erlaubt. Sie können also über alle Elemente hinweg iterieren und beim Hinzufügen zur Menge prüfen, ob die Länge geändert wurde und ob die Länge nicht geändert wurde, bedeutet, dass es doppelt ist und es der Liste hinzugefügt wird. Ihr nächster Satz wird also die Liste sein. und mach weiter so, es sei denn, deine Listengröße ist null. Es ist nur ein Hinweis darauf, dass dies hilft.

Happy Learning :)

Answer 3

Dieser sollte funktionieren. (Und wurde getestet)

ArrayList<ArrayList<String>> batches = new ArrayList<ArrayList<String>>(); 
    ArrayList<String> arr = new ArrayList<String>(); 

    arr.add("A"); 
    arr.add("B"); 
    arr.add("B"); 
    arr.add("A"); 
    arr.add("K"); 
    arr.add("B"); 
    arr.add("A"); 

    batches.add(new ArrayList<String>()); 

    int id = 0, arrID = 0; 

    while(arrID < arr.size()) 
    { 
     if(batches.get(id).contains(arr.get(arrID))) 
     { 
      id ++; 
      if(id+1 > batches.size()) 
       batches.add(new ArrayList<String>()); 
     } 
     else 
     { 
      batches.get(id).add(arr.get(arrID)); 
      arrID ++; 
      id = 0; 
     } 
    } 

    System.out.println("Results: "); 
    for(int i=0; i<batches.size(); i++) 
    { 
     System.out.println("Batch "+i); 
     for(int x=0; x<batches.get(i).size(); x++) 
      System.out.println(batches.get(i).get(x)); 
    } 

Answer 4

ich wahrscheinlich

Paket dummy eine Liste von Listen

zB tun würde;

importieren java.util.ArrayList; importieren java.util.List;

public class BatchIt {

/** 
* @param args 
*/ 
public static void main(String[] args) { 
    List<List<String>> batches = new ArrayList<List<String>>(); 
    List<String> firstBatch = new ArrayList<String>(); 
    batches.add(firstBatch); 
    for (String input : args) { 
     boolean inputAdded = false; 
     for (List<String> batch : batches) { 
      if(!batch.contains(input)){ 
       batch.add(input); 
       inputAdded = true; 
       break; 
      } 
     } 
     if(!inputAdded){ 
      List<String> nextBatch = new ArrayList<String>(); 
      nextBatch.add(input); 
      batches.add(nextBatch); 
     } 
    } 
    System.out.print(batches); 
} 

}