线性时间求出序列第 k 小

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Nth {
    /**
     * Integers with a subscript, to make sure all numbers
     * in the array are different.
     */
    public static class DistinctNumber implements Comparable<DistinctNumber> {
        private final int number, index;

        /**
         * @param _number the value of the number.
         * @param _index  the index of the number in the array.
         */
        public DistinctNumber(int _number, int _index) {
            this.number = _number;
            this.index = _index;
        }

        /**
         * @return the value of the number.
         */
        public int valueOf() {
            return number;
        }

        /**
         * Compare {@code this} and {@code b}. If the value of the two are the
         * same, compare the index.
         *
         * @param b the object to be compared.
         * @return an integer, if {@code x < y} then {@code x.compareTo(y)
         * < 0}, if {@code x > y} then {@code x.compare(y) > 0}, if {@code
         * x = y} then {@code x.compare(y) = 0}.
         */
        @Override
        public int compareTo(DistinctNumber b) {
            if (this.number != b.number) {
                return this.number - b.number;
            } else {
                return this.index - b.index;
            }
        }

        /**
         * Convert a {@code int[]} to {@code DistinctNumber[]}.
         *
         * @param intArray      the {@code int} array want to be converted.
         * @param distinctArray the {@code DistinctNumber} array want
         *                      to be saved into.
         * @return the array after converting.
         */
        public static DistinctNumber[] intArrayToDistinctArray(int[] intArray, DistinctNumber[] distinctArray) {
            for (int i = 0; i < intArray.length; ++i) {
                distinctArray[i] = new DistinctNumber(intArray[i], i);
            }
            return distinctArray;
        }

        /**
         * Convert a {@code int[]} to {@code DistinctNumber[]}.
         *
         * @param intArray the {@code int} array want to be converted.
         * @return the array after converting.
         */
        public static DistinctNumber[] intArrayToDistinctArray(int[] intArray) {
            DistinctNumber[] distinctArray = new DistinctNumber[intArray.length];
            return intArrayToDistinctArray(intArray, distinctArray);
        }

        /**
         * Convert a {@code DistinctNumber[]} to {@code int[]} .
         *
         * @param distinctArray the {@code DistinctNumber} array want
         *                      to be converted.
         * @param intArray      the {@code int} array want to be saved into.
         * @return the array after converting.
         */
        public static int[] distinctArrayToIntArray(DistinctNumber[] distinctArray, int[] intArray) {
            for (int i = 0; i < distinctArray.length; ++i) {
                intArray[i] = distinctArray[i].valueOf();
            }
            return intArray;
        }

        /**
         * Convert a {@code DistinctNumber[]} to {@code int[]} .
         *
         * @param distinctArray the {@code DistinctNumber} array want
         *                      to be converted.
         * @return the array after converting.
         */
        public static int[] distinctArrayToIntArray(DistinctNumber[] distinctArray) {
            int[] intArray = new int[distinctArray.length];
            return distinctArrayToIntArray(distinctArray, intArray);
        }
    }

    /**
     * Use Hoare partition method to move all the numbers
     * in the array smaller than {@code array[pivot]} to its front,
     * move all the numbers larger than it to its back, and
     * return the final position of the number.
     *
     * @param array a non-empty array wants to be rearranged.
     * @param pivot an integer from {@code 0} to
     *              {@code array.length - 1}, which represents
     *              the position of the pivot.
     * @return an integer from {@code 0} to {@code array.length - 1},
     * which represents the position of the pivot after rearranged.
     */
    public static int hoarePartition(DistinctNumber[] array, int pivot) {
        int left = 0, right = array.length - 1;

        while (left < right) {
            /*
            Find two positions left and right which
            satisfies that array[left] > array[pivot]
            > array[right] and left <= pivot <= right.
             */
            while (left < pivot &&
                    array[left].compareTo(array[pivot]) <= 0) {
                left++;
            }
            while (right > pivot &&
                    array[right].compareTo(array[pivot]) >= 0) {
                right--;
            }

            /*
            If pivot equals to left or right, which means
            the position of the pivot changes. So we have
            to change the position of the pivot before
            swapping left and right.
             */
            if (pivot == left) {
                pivot = right;
            } else if (pivot == right) {
                pivot = left;
            }

            /*
            Swap array[left] and array[right].
             */
            DistinctNumber temp = array[left];
            array[left] = array[right];
            array[right] = temp;
        }

        return pivot;
    }


    /**
     * Divide an array into every five integer a piece, extract
     * the median of each copy to the front end of the entire
     * array, copy the front and return it.
     *
     * @param array a non-empty {@code DistinctNumber} array want
     *              to be rearranged.
     * @return a non-empty array, contains the median of each
     * slice.
     */
    public static DistinctNumber[] divideIntoFive(DistinctNumber[] array) {
        List<DistinctNumber> mediumList = new LinkedList<>(); // Median of each slice
        List<DistinctNumber> remainList = new LinkedList<>(); // Numbers other than the median

        for (int beginSlice = 0; beginSlice < array.length; beginSlice += 5) {
            // Extract a slice.
            int endSlice = Integer.min(beginSlice + 5, array.length);
            DistinctNumber[] slice = Arrays.copyOfRange(array, beginSlice, endSlice);

            // Sort the slice and assign each number to each linked list
            Arrays.sort(slice);
            for (int i = 0; i < slice.length; ++i) {
                if (i == slice.length / 2) {
                    mediumList.add(slice[i]);
                } else {
                    remainList.add(slice[i]);
                }
            }
        }

        // Copy mediumList and remainList to the array.
        int indexOfChangedArray = 0;
        for (DistinctNumber medium : mediumList) {
            array[indexOfChangedArray] = medium;
            indexOfChangedArray++;
        }
        for (DistinctNumber remain : remainList) {
            array[indexOfChangedArray] = remain;
            indexOfChangedArray++;
        }

        // Convert mediumList to array and return.
        DistinctNumber[] mediumArray = new DistinctNumber[mediumList.size()];
        mediumList.toArray(mediumArray);
        return mediumArray;
    }


    /**
     * Give an {@code DistinctNumber} array and a number n,
     * rearrange the array to make that for all {@code i < n},
     * {@code array[i] <= array[n]}; for all {@code i > n},
     * {@code array[i] >= array[n]}.
     *
     * @param array a non-empty {@code DistinctNumber} array want
     *              to be rearranged.
     * @param n     an integer from {@code 0} to {@code n - 1}.
     */
    public static void nthElement(DistinctNumber[] array, int n) {
        if (n >= array.length) {
            throw new ArrayIndexOutOfBoundsException("n cannot " +
                    "greater than the size of array");
        }

        // Recursion bounds
        if (array.length <= 10) {
            Arrays.sort(array);
            return;
        }

        // Get the pivot
        DistinctNumber[] mediumOfSlice = divideIntoFive(array);
        nthElement(mediumOfSlice, mediumOfSlice.length / 2);
        int pivot = mediumOfSlice.length / 2;
        System.arraycopy(mediumOfSlice, 0, array, 0, mediumOfSlice.length);
        pivot = hoarePartition(array, pivot);

        // Divide and conquer by pivot
        if (n < pivot) {
            DistinctNumber[] leftSide = Arrays.copyOfRange(array, 0, pivot);
            nthElement(leftSide, n);
            System.arraycopy(array, 0, leftSide, 0, leftSide.length);
        } else if (n > pivot) {
            DistinctNumber[] rightSide = Arrays.copyOfRange(array, pivot + 1, array.length);
            nthElement(rightSide, n - pivot - 1);
            System.arraycopy(array, pivot + 1, rightSide, 0, rightSide.length);
        }
    }

    /**
     * Give an array and a number n, rearrange the array to make
     * that for all {@code i < n}, {@code array[i] <= array[n]};
     * for all {@code i > n}, {@code array[i] >= array[n]}.
     *
     * @param array a non-empty array want to be rearranged.
     * @param n     an integer from {@code 0} to {@code n - 1}.
     */
    public static void nthElement(int[] array, int n) {
        DistinctNumber[] distinctArray = DistinctNumber.intArrayToDistinctArray(array);
        nthElement(distinctArray, n);
    }
}