Что эквивалентная функция "nth_element" в Java?

Ответ 1

Стандартная библиотека Java не содержит эквивалент алгоритма С++ nth_element. Самое близкое, что вы получите, это использовать Collections.sort.

В качестве альтернативы вы можете попробовать реализовать свою собственную версию этой функции. Вы можете реализовать nth_element путем выполнения стандартной сортировки и вызова Collections.sort, хотя в зависимости от ваших требований времени это может быть слишком медленным. Существует множество специализированных алгоритмов для выполнения такого рода переупорядочения, которые называются алгоритмами выбора, и на странице Википедии по теме есть несколько хороших примеров. Эмпирически самый быстрый алгоритм называется quickselect и основан на алгоритме быстрой сортировки; он работает в ожидаемое время O (n), но может деградировать до O (n ²) для патологически плохих входов. Существует известный (и, как известно, сложный) алгоритм, иногда называемый алгоритмом медианы медианов, который работает в худшем случае 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);
}