Java-Äquivalent von C++ Equal_range (oder Lower_bound & Outer_bound)

Question

Ich habe eine Liste von Objekt sortiert und ich möchte das erste Vorkommen und das letzte Vorkommen eines Objekts finden. In C++ kann ich problemlos std :: equal_range (oder nur einen unteren und einen oberen) verwenden.

Zum Beispiel:

bool mygreater (int i,int j) { return (i>j); } 

int main() { 
    int myints[] = {10,20,30,30,20,10,10,20}; 
    std::vector<int> v(myints,myints+8);       // 10 20 30 30 20 10 10 20 
    std::pair<std::vector<int>::iterator,std::vector<int>::iterator> bounds; 

    // using default comparison: 
    std::sort (v.begin(), v.end());        // 10 10 10 20 20 20 30 30 
    bounds=std::equal_range (v.begin(), v.end(), 20);   //  ^ ^

    // using "mygreater" as comp: 
    std::sort (v.begin(), v.end(), mygreater);     // 30 30 20 20 20 10 10 10 
    bounds=std::equal_range (v.begin(), v.end(), 20, mygreater); //  ^ ^

    std::cout << "bounds at positions " << (bounds.first - v.begin()); 
    std::cout << " and " << (bounds.second - v.begin()) << '\n'; 

    return 0; 
} 

In Java, scheint es keine einfache Gleichwertigkeit zu sein? Wie soll ich mit dem gleichen Bereich zu tun mit

List<MyClass> myList; 

By the way, ich einen Standard-Import java.util.List bin mit;

Answer 1

In Java verwenden Sie Collections.binarySearch, um die untere Grenze des gleichen Bereichs in einer sortierten Liste zu finden (Arrays.binarySearch bietet eine ähnliche Funktion für Arrays). Dann fahren Sie fort, linear zu iterieren, bis Sie bis zum Ende der gleichen Entfernung treffen.

Diese Methoden funktionieren für Methoden, die die Schnittstelle Comparable implementieren. Für Klassen, die Comparable nicht implementieren, können Sie eine Instanz benutzerdefinierteComparator für den Vergleich der Elemente Ihres bestimmten Typs liefern.

Answer 2

Sie können so etwas wie dies versuchen:

public class TestSOF { 

     private ArrayList <Integer> testList = new ArrayList <Integer>(); 
     private Integer first, last; 

     public void fillArray(){ 

      testList.add(10); 
      testList.add(20); 
      testList.add(30); 
      testList.add(30); 
      testList.add(20); 
      testList.add(10); 
      testList.add(10); 
      testList.add(20); 
     } 

     public ArrayList getArray(){ 

      return this.testList; 
     } 

     public void sortArray(){ 

      Collections.sort(testList); 
     } 

     public void checkPosition(int element){ 

      if (testList.contains(element)){ 

       first = testList.indexOf(element); 
       last = testList.lastIndexOf(element); 

       System.out.println("The element " + element + "has it's first appeareance on position " 
      + first + "and it's last on position " + last); 
      } 

      else{ 

       System.out.println("Your element " + element + " is not into the arraylist!"); 
      } 
     } 

     public static void main (String [] args){ 

      TestSOF testSOF = new TestSOF(); 

      testSOF.fillArray(); 
      testSOF.sortArray(); 
      testSOF.checkPosition(20); 
     } 

}

Answer 3

In binären Suche, wenn Sie das Element finden, dann können Sie auf seine verlassen, um zu tun binäre Suche halten erste Vorkommen zu finden und zu richtig, um das letzte Element zu finden.

/* 
B: element to find first or last occurrence of 
searchFirst: true to find first occurrence, false to find last 
*/ 
Integer bound(final List<Integer> A,int B,boolean searchFirst){ 
    int n = A.size(); 
    int low = 0; 
    int high = n-1; 
    int res = -1; //if element not found 
    int mid ; 
    while(low<=high){ 
     mid = low+(high-low)/2; 
     if(A.get(mid)==B){ 
      res=mid; 
      if(searchFirst){high=mid-1;} //to find first , go left 
      else{low=mid+1;}    // to find last, go right 
     } 
     else if(B>A.get(mid)){low=mid+1;} 
     else{high=mid-1;} 
    } 
    return res; 
} 

Answer 4

import java.io.BufferedReader; 
import java.io.BufferedWriter; 
import java.io.IOException; 
import java.io.InputStreamReader; 
import java.io.OutputStreamWriter; 
import java.util.Collections; 
import java.util.Vector; 

public class Bounds { 

    public static void main(String[] args) throws IOException { 
     Vector<Float> data = new Vector<>(); 
     for (int i = 29; i >= 0; i -= 2) { 
      data.add(Float.valueOf(i)); 
     } 
     Collections.sort(data); 
     float element = 14; 
     BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); 
     BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out)); 
     String string = bf.readLine(); 
     while (!string.equals("q")) { 
      element=Float.parseFloat(string); 
      int first = 0; 
      int last = data.size(); 
      int mid; 
      while (first < last) { 
       mid = first + ((last - first) >> 1); 
       if (data.get(mid) < element) //lower bound. for upper use <= 
        first = mid + 1; 
       else 
        last = mid; 
      } 
      log.write("data is: "+data+"\n"); 
      if(first==data.size()) 
       first=data.size()-1; 
      log.write("element is : " + first+ "\n"); 
      log.flush(); 
      string= bf.readLine(); 
     } 
     bf.close(); 
    } 

} 

Dies ist die Implementierung für lower_bound und upper_bound ähnlich wie C++: Die Idee sollte mit dem Code klar sein. Beachten Sie, dass das Element, nach dem Sie suchen, nicht im Vektor oder in der Liste vorhanden sein muss. Diese Implementierung gibt nur die oberen und unteren Grenzen des Elements an.