Wie finden Sie Elemente, die mit einer Sub-String innerhalb einer sortierten ArrayList beginnen?

Question

Ich habe eine sortierte ArrayList von 33000 Elementen mit Java, wie kann ich nur die Elemente auflisten, die mit einem Teilstring beginnen.

Zum Beispiel: Ich habe eine Zeichenfolge "Luft". Also brauche ich jedes Wort, das mit "air" ("airplane", "airforce", "airline" usw.) beginnt.

Gibt es eine Möglichkeit, dies zu tun, ohne nacheinander zu iterieren? So

Answer 1

, da Sie haben eine ArrayList<String> sortiert words, die Sie tun können:

String prefix = "air"; 
int start = Collections.binarySearch(words, prefix); 
// index of prefix OR -(insertion point) - 1 
if (start < 0) // prefix is not contained as a whole word 
    start = -start - 1; 
int end = start; 
while (end < words.size() && words.get(end).startsWith(prefix)) 
    end++; 
List<String> prefixWords = words.subList(start, end); 

Die binäre Suche ist O(log(N)) und das Aufschneiden ist O(K) wo K ist die Länge der Unterliste (Anzahl der „Luft“ - vorfixierte Wörter). Also, das sollte viel besser sein, als über die Liste zu iterieren, zumindest über verschiedene Präfixe verteilt (im schlimmsten Fall, dass alle Wörter mit Präfix beginnen).

Answer 2

Wenn Sie die Anzahl der Elemente, die mit "air" beginnen, nicht kennen, wird Ihre Suche in der Reihenfolge O (n) erfolgen. Es gibt keine Brute-Force-Methode oder Balancebaumsuche, die Sie ausführen können, um dies in weniger als O (n) zu erreichen.

Answer 3

Binary Suche wäre zunächst goto wie

public static int binarySearch(ArrayList<String> sortedArray,String find){ 
     int lowerBound=0; 
     int upperBound=sortedArray.size()-1; 

     while(true){ 
      int midIndex=lowerBound+((upperBound-lowerBound)/2); 
      String curr=sortedArray.get(midIndex); 
      if(upperBound<lowerBound){ 
       System.out.println("word not found"); 
       return -1; 
      } 

      if (curr.equals(find)) 
       return midIndex; 

      if(curr.compareTo(find)>0) 
       upperBound=midIndex-1; 

      if(curr.compareTo(find)<0) 
       lowerBound=midIndex+1; 
     } 
    } 

Dann, nachdem Sie Index Iterierte über die Liste nach links bekam und rechts, bis entweder Sie Ende Trefferliste/Anfang oder ein Präfix unterscheidet sich von dem youre suchen für

 public static ArrayList<String> makeList(ArrayList<String> sortedArray,String startingWith){ 
     ArrayList<String> result=new ArrayList<>(); 
     ArrayList<String> temp=new ArrayList<>(sortedArray.size());    

     for(int i=0;i<sortedArray.size();i++){ 
      temp.add(" "); 
     } 

     //copy sortedArray to temp 
     for(String s: sortedArray){ 
      if(s.length()>startingWith.length()) { 
       temp.set(sortedArray.indexOf(s), s.substring(0, startingWith.length())); 
      } else temp.set(sortedArray.indexOf(s),s); 

     } 


     int index=binarySearch(temp,startingWith); 
     result.add(sortedArray.get(index)); 

     int leftIndex=index; 
     int rightIndex=index;   
     while(true){ 

      //if left and right index dont go out of bounds cont. iterating 
      if ((leftIndex - 1) >= 0) leftIndex--; 
      if ((rightIndex + 1) < sortedArray.size()) rightIndex++; 

      //if left and right index are at end of list return 
      if((rightIndex>=sortedArray.size()) && (leftIndex<0)) return result; 

      boolean isLeft; 
      boolean isRight; 

      if(sortedArray.get(leftIndex).length()>startingWith.length()) { 
       isLeft = sortedArray.get(leftIndex).substring(0,startingWith.length()).equals(startingWith); 
      }else isLeft=false; 


      if(sortedArray.get(rightIndex).length()>startingWith.length()) { 
       isRight = sortedArray.get(rightIndex).substring(0,startingWith.length()).equals(startingWith); 
      }else isRight=false; 

      if(!isLeft && !isRight) return result; 


      if(isRight) result.add(sortedArray.get(rightIndex)); 
      if(isLeft) result.add(sortedArray.get(leftIndex)); 

     } 

    }