21

我有一个排序的对象列表,我想找到对象的第一次出现和最后一次出现。在 C++ 中,我可以轻松地使用 std::equal_range (或者只有一个 lower_bound 和一个 upper_bound)。

例如:

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

在Java中,似乎没有简单的等价?我应该如何处理相等的范围

List<MyClass> myList;

顺便说一句,我使用的是标准导入 java.util.List;

4

9 回答 9

11

在 Java 中,您可以使用Collections.binarySearch在排序列表中查找相等范围的下限(Arrays.binarySearch为数组提供了类似的功能)。这为您提供了相同范围内的位置,而没有进一步的保证:

如果列表包含多个等于指定对象的元素,则无法保证会找到哪一个。

然后你线性地向前然后向后迭代,直到你到达相等范围的末端。

这些方法适用于实现Comparable接口的对象。对于不实现 的类Comparable,您可以提供一个自定义 Comparator实例来比较您的特定类型的元素。

于 2013-03-24T20:56:00.007 回答
8

我们可以借助 java 库函数以及定义我们自己的LowerBound 和 UpperBound 函数来找到下界和上界。

{#情况1}

如果数字不存在,则下限和上限将相同。即在这种情况下,lbub将是数组的插入点,即应该插入数字以保持数组排序的点。

示例 1:

6 1 // 6 is the size of the array and 1 is the key
2 3 4 5 6 7 here lb=0 and ub=0 (0 is the position where 1 should be inserted to keep the array sorted)

6 8 // 6 is the size of the array and 8 is the key
2 3 4 5 6 7  here lb=6 and ub=6 (6 is the position where 8 should be inserted to keep the array sorted)

6 3 // 6 is the size of the array and 3 is the key
1 2 2 2 4 5  here lb=4 and ub=4 (4 is the position where 3 should be inserted to keep the array sorted)


    

{#case-2(a)}

如果数字存在且频率为 1。即出现次数为 1

lb =该数字的索引。
ub =下一个数字的索引,它刚好大于数组中的那个数字。即ub =那个数字的索引+1

示例 2:

6 5 // 6 is the size of the array and 5 is the key
1 2 3 4 5 6 here lb=4 and ub=5
    

{#case-2(b)}

如果数字存在并且频率超过 1。数字出现多次。在这种情况下 , lb将是该数字第一次出现的索引。 ub将是该数字+1 的最后一次出现的索引。即,该数字的索引刚好大于数组中的键。

示例 3:

 11 5 // 11 is the size of the array and 5 is the key
 1 2 3 4 5 5 5 5 5 7 7 here lb=4 and ub=9

Lower_Bound 和 Upper_Bound 的实现

方法一: 通过库函数

// a 是数组,x 是目标值

int lb=Arrays.binarySearch(a,x); // for lower_bound

int ub=Arrays.binarySearch(a,x); // for upper_bound

if(lb<0) {lb=Math.abs(lb)-1;}//if the number is not present

else{ // if the number is present we are checking 
    //whether the number is present multiple times or not
    int y=a[lb];
    for(int i=lb-1; i>=0; i--){
        if(a[i]==y) --lb;
        else break;
    }
}
  if(ub<0) {ub=Math.abs(ub)-1;}//if the number is not present

  else{// if the number is present we are checking 
    //whether the number is present multiple times or not
    int y=a[ub];
    for(int i=ub+1; i<n; i++){
        if(a[i]==y) ++ub;
        else break;
    }
    ++ub;
}

方法2: 通过定义自己的功能

//对于下界

static int LowerBound(int a[], int x) { // x is the target value or key
  int l=-1,r=a.length;
  while(l+1<r) {
    int m=(l+r)>>>1;
    if(a[m]>=x) r=m;
    else l=m;
  }
  return r;
}

// 对于 Upper_Bound

 static int UpperBound(int a[], int x) {// x is the key or target value
    int l=-1,r=a.length;
    while(l+1<r) {
       int m=(l+r)>>>1;
       if(a[m]<=x) l=m;
       else r=m;
    }
    return l+1;
 }

     

或者我们可以使用

int m=l+(r-l)/2;

但是如果我们使用

int m=(l+r)>>>1; // it is probably faster

但是使用上述任何计算 m 的公式都会防止溢出

在 C 和 C++ 中 (>>>) 运算符不存在,我们可以这样做:

int m= ((unsigned int)l + (unsigned int)r)) >> 1;

// 程序中的实现:

import java.util.*;
import java.lang.*;
import java.io.*;
public class Lower_bound_and_Upper_bound {

public static void main (String[] args) throws java.lang.Exception
{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer s = new StringTokenizer(br.readLine());
    int n=Integer.parseInt(s.nextToken()),x=Integer.parseInt(s.nextToken()),a[]=new int[n];
    s = new StringTokenizer(br.readLine());
    for(int i=0; i<n; i++) a[i]=Integer.parseInt(s.nextToken());
    Arrays.sort(a);// Array should be sorted. otherwise lb and ub cant be calculated
    int u=UpperBound(a,x);
    int l=LowerBound(a,x);
    System.out.println(l+" "+u);
 }
}

# 计算下界和上界的等效 C++ 代码

  #include<bits/stdc++.h>
  #define IRONMAN ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  using namespace std;
  typedef long long int ll;
  int main() {
    IRONMAN
    int n,x;cin>>n>>x;
    vector<int> v(n);
    for(auto &i: v) cin>>i;
    ll lb=(lower_bound(v.begin(),v.end(),x))-v.begin();// for calculating lb
    ll ub=(upper_bound(v.begin(),v.end(),x))-v.begin();// for calculating ub
    cout<<lb<<" "<<ub<<"\n";
    return 0;
  }
于 2020-09-12T00:04:14.800 回答
3

Java 已经内置了二进制搜索功能,可以计算数组中元素的下限/上限,无需实现自定义方法。

当我们谈论上限/下限或相等范围时,我们总是指容器的索引(在这种情况下为 ArrayList),而不是包含的元素。让我们考虑一个数组(我们假设数组是排序的,否则我们先排序):

List<Integer> nums = new ArrayList<>(Arrays.asList(2,3,5,5,7,9,10,18,22));

“下界”函数必须返回数组的索引,必须在其中插入元素以保持数组排序。“上限”必须返回数组中最小元素的索引,即大于查找的元素。例如

lowerBound(nums, 6)

必须返回 3,因为 3 是数组的位置(从 0 开始计数),其中必须插入 6 以保持数组排序。

upperBound(nums, 6)

必须返回 4,因为 4 是数组中最小元素的位置,即大于5 或​​ 6,(位置 4 上的数字 7)。

在标准库中的 C++ 中,这两种算法都已在标准库中实现。在 Java 中,您可以使用

Collections.binarySearch(nums, element)

对数时间复杂度计算位置。

如果数组包含元素,Collections.binarySearch返回元素的第一个索引(在上面的数组 2 中)。否则,它返回一个负数,指定下一个更大元素在数组中的位置,从数组的最后一个索引开始倒数。在此位置找到的数字是数组中比您要查找的元素大的最小元素。

例如,如果您调用

int idx = Collections.binarySearch(nums, 6)

该函数返回-5。如果从数组的最后一个索引(-1、-2、...)倒数,索引 -5 指向数字 7——数组中大于元素 6 的最小数字。

结论:如果排序后的数组中包含查找的元素,则下限为该元素的位置,上限为下一个较大元素的位置。

如果数组不包含元素,则下界为位置

Math.abs(idx) - 2

上限是位置

Math.abs(idx) - 1

在哪里

idx = Collections.binarySearch(nums, element)

请始终牢记边境案件。例如,如果您在上面指定的数组中查找 1:

idx = Collections.binarySearch(nums, 1)

该函数返回-1。因此,upperBound = Math.abs(idx) - 1 = 0 - 位置 0 处的元素 2。但元素 1 没有下界,因为 2 是数组中的最小数字。相同的逻辑适用于大于数组中最大数字的元素:如果您查找数字 25 的下限/上限,您将得到

  idx = Collections.binarySearch(nums, 25) 

ix = -10。可以计算下界:lb = Math.abs(-10) - 2 = 8,也就是数组的最后一个索引,但是没有上界,因为22已经是数组中最大的元素,没有位置 9 的元素。

equal_range 指定数组的所有索引,范围从下限索引开始到(但不包括)上限。例如,上面数组中数字 5 的相等范围是索引

 [2,3]

数字 6 的相等范围是空的,因为数组中没有数字 6。

于 2019-09-04T12:45:34.830 回答
2

cpp 中的 Java 等价的 lower_bound 是

public static int lower(int arr[],int key){
    int low = 0;
    int high = arr.length-1;
    while(low < high){
        int mid = low + (high - low)/2;
        if(arr[mid] >= key){
            high = mid;
        }
        else{
            low = mid+1;
        }
    }
    return low;
}

但是如果键不存在于数组中,上面的代码片段将给出下限

cpp中upper_bound的Java等价物是

public static int upper(int arr[],int key){
    int low = 0;
    int high = arr.length-1;
    while(low < high){
        int mid = low + (high - low+1)/2;
        if(arr[mid] <= key){
            low = mid;
        }
        else{
            high = mid-1;
        }
    }
    return low;
}

但是如果键不存在于数组中,上面的代码片段将给出键的下限

于 2020-05-31T14:27:02.283 回答
0

你可以尝试这样的事情:

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);
    } 
}
于 2013-03-24T21:08:45.267 回答
0

在二分查找中,当您找到元素时,您可以继续向其左侧进行二分搜索以找到第一个出现的位置,并继续向右进行二分搜索以找到最后一个元素。代码应该清楚这个想法:

/*
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;
}
于 2015-06-15T05:39:43.770 回答
0

如果您想在不定义自己的方法的情况下找到 lower_bound 并从头开始做所有事情,请使用以下代码片段。您可能已经注意到,此方法仅适用于原始数组,不适用于 ArrayList,因为我们在 Collections 类中没有指定 Binaryserach 的开始停止索引的函数(从 java16 开始)。

  • al 是一个数组(String[] al = new String[N];)
  • token是我们在数组中寻找的。
Arrays.sort(al, 0, N); 
int index = Arrays.binarySearch(al, 0, N , token);
while(index > 0 && al[index].equals(al[index - 1])){
       index = Arrays.binarySearch(al, 0, index, token); //lower_bound in java.
}

对于上限,您可以轻松修改代码。

于 2021-09-17T12:19:15.207 回答
0

以这种方式尝试下限和上限。它很容易实现。

import java.util.Arrays;

class LowerBoundUpperBound{
    public static void main(String[] args) {
        int a[] = {1, 2, 3, 4, 5, 5, 5, 5, 5, 7, 7};

        int key = 5;
        int pos = Arrays.binarySearch(a, key);
        int lb = (pos < 0) ? ~pos - 1 : getlb(pos, a);
        int ub = (pos < 0) ? ~pos : getUb(pos, a);

        System.out.println("Lower Bound=" + lb);
        System.out.println("Upper Bound=" + ub);

        // You can also try on a[] = {1 ,2 ,3 ,4 ,5 ,6};
        // For key=5, lb=3 and ub=5


    }

    private static int getlb(int pos, int[] a) {
        while (pos - 1 >= 0 && a[pos] == a[pos - 1]) pos--;
        return pos - 1;
    }

    private static int getUb(int pos, int[] a) {
        while (pos + 1 < a.length && a[pos] == a[pos + 1]) pos++;
        return pos + 1;

    }
}

注意:执行上述方法时必须对数组进行排序。

于 2021-06-23T06:08:34.770 回答
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();
    }

}

这是类似于 c++ 的 lower_bound 和 upper_bound 的实现。请注意,您要搜索的元素不必出现在向量或列表中。这个实现只给出了元素的上限和下限。

于 2017-08-21T19:34:58.773 回答