Java等价于c ++ equal_range(或lower_bound&upper_bound)

Question

我有一个对象列表排序,我想找到一个对象的第一次出现和最后一次出现.在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;

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

Answer 1

在Java中,您可以使用Collections.binarySearch在排序列表中查找相等范围的下限(Arrays.binarySearch为数组提供类似的功能).然后继续线性迭代,直到达到相等范围的末尾.

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

Answer 2

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

{＃情况1}

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

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

// 用于上界

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