Równowaga Java z C++ equal_range (lub lower_bound & upper_bound)

Question

Mam listę obiektów posortowanych i chcę znaleźć pierwsze wystąpienie i ostatnie wystąpienie obiektu. W C++, mogę łatwo użyć std :: equal_range (lub tylko jeden lower_bound i jeden upper_bound).

Na przykład:

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; 
} 

w Javie, nie wydaje się być prosta równoważność? Jak zrobić z jednakowym zakresie z

List<MyClass> myList; 

Nawiasem mówiąc, używam standardowego import java.util.List;

Answer 1

W Javie używa się Collections.binarySearch do znalezienia dolnej granicy równego zakresu na posortowanej liście (Arrays.binarySearch zapewnia podobną możliwość dla tablic). Następnie kontynuujesz iterację liniową, aż dotrzesz do końca równego zakresu. Ta metoda działa dla metod implementujących interfejs Comparable. W przypadku klas, które nie implementują Comparable, można dostarczyć instancję niestandardowego obiektu Comparator w celu porównania elementów określonego typu.

Answer 2

Można spróbować czegoś takiego:

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

w poszukiwaniu binarnym, gdy znajdziesz elementu następnie można dalej robić przeszukiwanie binarne w swoją lewą stronę, aby znaleźć pierwsze wystąpienie oraz do w prawo, aby znaleźć ostatni element. Pomysł powinien być przezroczysty z kodem:

/* 
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(); 
    } 

} 

Jest to realizacja dla LOWER_BOUND i UPPER_BOUND podobny do C++. Należy zauważyć, że szukany element nie musi znajdować się w wektorze lub na liście. Ta implementacja daje tylko górne i dolne ograniczenie elementu.