Что эквивалентная функция "nth_element" в Java?
Я не хочу получать отсортированный массив, только значение n-го элемента. Например, учитывая массив
a = [20, 5, 1, -3]
Я хотел бы иметь возможность запросить
nth_element(a,2) = 1
В С++ существует функция std::nth_element
, которая может это сделать. Существует ли эквивалентная функция Java?
Спасибо!
Ответы
Ответ 1
Стандартная библиотека Java не содержит эквивалент алгоритма С++ nth_element
. Самое близкое, что вы получите, это использовать Collections.sort
.
В качестве альтернативы вы можете попробовать реализовать свою собственную версию этой функции. Вы можете реализовать nth_element
путем выполнения стандартной сортировки и вызова Collections.sort
, хотя в зависимости от ваших требований времени это может быть слишком медленным. Существует множество специализированных алгоритмов для выполнения такого рода переупорядочения, которые называются алгоритмами выбора, и на странице Википедии по теме есть несколько хороших примеров. Эмпирически самый быстрый алгоритм называется quickselect и основан на алгоритме быстрой сортировки; он работает в ожидаемое время O (n), но может деградировать до O (n 2) для патологически плохих входов. Существует известный (и, как известно, сложный) алгоритм, иногда называемый алгоритмом медианы медианов, который работает в худшем случае O (n), но имеет высокий постоянный коэффициент, который мешает ему использовать на практике.
Надеюсь, это поможет!
Ответ 2
Вот реализация Java nth_element:
class Nth_element
{
static void nth_element_helper2(double[] arr, int beg, int end)
{
for(int i = beg + 1; i < end; i++)
{
for(int j = i; j > beg; j--)
{
if(arr[j - 1] < arr[j])
break;
double t = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = t;
}
}
}
static void nth_element_helper(double[] arr, int beg, int end, int index)
{
if(beg + 4 >= end)
{
nth_element_helper2(arr, beg, end);
return;
}
int initial_beg = beg;
int initial_end = end;
// Pick a pivot (using the median of 3 technique)
double pivA = arr[beg];
double pivB = arr[(beg + end) / 2];
double pivC = arr[end - 1];
double pivot;
if(pivA < pivB)
{
if(pivB < pivC)
pivot = pivB;
else if(pivA < pivC)
pivot = pivC;
else
pivot = pivA;
}
else
{
if(pivA < pivC)
pivot = pivA;
else if(pivB < pivC)
pivot = pivC;
else
pivot = pivB;
}
// Divide the values about the pivot
while(true)
{
while(beg + 1 < end && arr[beg] < pivot)
beg++;
while(end > beg + 1 && arr[end - 1] > pivot)
end--;
if(beg + 1 >= end)
break;
// Swap values
double t = arr[beg];
arr[beg] = arr[end - 1];
arr[end - 1] = t;
beg++;
end--;
}
if(arr[beg] < pivot)
beg++;
// Recurse
if(beg == initial_beg || end == initial_end)
throw new RuntimeException("No progress. Bad pivot");
if(index < beg) // This is where we diverge from QuickSort. We only recurse on one of the two sides. This is what makes nth_element fast.
nth_element_helper(arr, initial_beg, beg, index);
else
nth_element_helper(arr, beg, initial_end, index);
}
static double nth_element(double[] arr, int index)
{
nth_element_helper(arr, 0, arr.length, index);
return arr[index];
}
public static void main(String[] args)
{
double[] arr = { 9, 7, 1, 5, 6, 4, 3, 2, 8, 0, 10 };
if(nth_element(arr, 5) == 5)
System.out.println("seems to work");
else
System.out.println("broken");
}
}
Ответ 3
Алгоритм быстрого выбора теперь реализован в библиотеке AlgART: https://bitbucket.org/DanielAlievsky/algart/src/master/src/main/java/net/algart/arrays/ArraySelector.java Вы можете просто использовать его через Maven, как описано здесь: http://algart.net/java/AlgART/
Ответ 4
В Java я думаю, что вы должны его реализовать, что-то вроде этого:
Integer nth_smallest_element(Integer[] originalArray, n) {
if (n >= originalArray.length)
throw new RuntimeException("Invalid index");
// Don't pass in your array, if you don't want it to be modified. Instead add them all later.
List<Integer> copyList = new ArrayList<Integer>();
copyList.addAll(originalArray);
Collections.sort(copyList);
return copyList.get(n);
}