Java-эквивалент C++ equal_range (или lower_bound & upper_bound)
У меня отсортирован список объектов, и я хочу найти первое и последнее вхождение объекта. В 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;
10 ответов
В Java вы используете Collections.binarySearch найти нижнюю границу равного диапазона в отсортированном списке (Arrays.binarySearch обеспечивает аналогичную возможность для массивов). Затем продолжите линейную итерацию, пока не дойдете до конца равного диапазона.
Эти методы работают для методов, реализующих Comparable интерфейс. Для классов, которые не реализуют ComparableВы можете предоставить экземпляр пользовательского Comparator для сравнения элементов вашего конкретного типа.
Мы можем найти нижнюю границу и верхнюю границу с помощью функции библиотеки 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
Метод-1:По функции библиотеки
// 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;
}
В 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 (число 7 на позиции 4).
В 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 - элемент 2 в позиции 0. Но для элемента 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.
Java-эквивалент lower_bound в cpp:
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;
}
Но приведенный выше фрагмент даст нижнюю границу, если ключ отсутствует в массиве.
Java-эквивалент upper_bound в cpp:
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;
}
Но приведенный выше фрагмент даст нижнюю границу ключа, если ключ отсутствует в массиве.
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();
}
}
Это реализация для lower_bound и upper_bound, похожая на C++. Обратите внимание, что искомый элемент не обязательно должен присутствовать в векторе или списке. Эта реализация дает только верхнюю и нижнюю границы элемента.
Если вы хотите найти 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.
}
Для верхней границы вы можете легко изменить код.
В бинарном поиске, когда вы находите элемент, вы можете продолжать выполнять бинарный поиск слева, чтобы найти первое вхождение, и вправо, чтобы найти последний элемент. Идея должна быть ясна с кодом:
/*
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;
}
Попробуйте таким же образом для нижней и верхней границ. Легко реализовать.
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;
}
}
Примечание. При выполнении описанного выше метода массив необходимо отсортировать.
Вы можете попробовать что-то вроде этого:
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);
}
}
Просто используйте бинарный поиск
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;
}