Java-äquivalent zu c++ equal_range (oder lower_bound & upper_bound)

Ich habe eine Liste von Objekten sortiert und ich auf der Suche nach dem ersten auftreten und dem letzten vorkommen eines Objekts an. In C++ kann ich problemlos verwenden std::equal_range (oder nur einen lower_bound und eine upper_bound).

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 äquivalenz? Wie soll ich mit der gleichen range mit 

List<MyClass> myList;

Übrigens, ich bin mit einem standard-import von java.util.Liste;

  • Für diejenigen von uns, die sprechen nicht "C", können Sie beschreiben, was Sie wollen in Englisch mit Beispielen?
InformationsquelleAutor Gob00st | 2013-03-24
  1. 5

    In Java verwenden Sie Sammlungen.binarysearch-Methode zu finden, die untere Grenze der gleiche Bereich in einer sortierten Liste (Arrays.binarySearch bietet eine ähnliche Funktion für arrays). Dann sind Sie weiterhin Linear Durchlaufen, bis Sie auf dem Ende des equal-range.

    Funktionieren diese Methoden bei den Methoden der Umsetzung der Vergleichbar - Schnittstelle. Für Klassen, die implementiert nicht die Comparable können Sie liefern eine Instanz einer benutzerdefinierte Comparator für den Vergleich der Elemente des bestimmten Typs.

    • Danke, aber es scheint, meine Liste ist nicht kompatibel mit ihm ? warum ?Die Methode binarysearch-Methode(List<? erweitert T>, T, Komparator<? super T>) in der Art der Sammlungen ist nicht anwendbar für die Argumente (Liste<MyDerivedData>, Datum, Komparator<BaseData>)
    • Ich habe versucht zu bewegen, der Komparator der Abgeleiteten Klasse MyDerivedData, aber immer noch habe ich dieses problem. Meine Liste ist einfach definiert als Liste<MyDerivedData> myList; Ist hier ein problem ? vielen Dank.
    • Werfen Sie einen Blick auf das update auf die Antwort.
    • Ich habe es versucht, aber es scheint die binäre Suche nicht wieder nur die 1. passende element. Bedeutung, wenn es doppelte Wert, binäre Suche Rückkehr zufälliges des gleichen Elements,...
    • Du hast Recht, ich Las die Dokumente, und es sieht aus wie der Algorithmus stellt keine Garantie für die Lage der zurückgegebene Wert in einem gleichen Bereich.
    • Dann was sollte ich mit Java !
    • siehe meinen anderen post hier um dieses Problem zu veranschaulichen - stackoverflow.com/questions/15606219/...

    InformationsquelleAutor dasblinkenlight
  2. 0

    Können Sie versuchen, so etwas wie dieses:

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

    }

    • Ich muss eine benutzerdefinierte Komparator...
    InformationsquelleAutor Survivor
  3. 0

    In binäre Suche , wenn Sie finden, das element, dann Sie können halten Sie tun binäre Suche auf der linken Seite, um zu finden, die ersten vorkommen und nach rechts, um zum letzten element.
    Die Idee sollte klar sein mit dem code: 

    /*
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;
}
    InformationsquelleAutor RJN_WLY
  4. 0
    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 Umsetzung für lower_bound und upper_bound ähnlich zu c++.
    Beachten Sie, dass das element, das Sie suchen, brauchen sich nicht in der Vektor oder Liste. Diese Implementierung gibt nur das element der oberen und unteren Schranken.

    InformationsquelleAutor HariUserX
  5. 0

    Nur binäre Suche

    private static int lowerBound(int[] a, int low, int high, int element){
    while(low < high){
        int middle = low + (high - low)/2;
        if(element > a[middle])
            low = middle + 1;
        else 
            high = middle;
    }
    return low;
}


private static int upperBound(int[] a, int low, int high, int element){
    while(low < high){
        int middle = low + (high - low)/2;
        if(a[middle] > element)
            high = middle;
        else 
            low = middle + 1;
    }
    return low;
}
    InformationsquelleAutor Ankit Sharma
Schreibe einen Kommentar