Найти топ N элементов в массиве

Question

Какое было бы наилучшее решение, чтобы найти верхние N (скажем, 10) элементов в неупорядоченном списке (скажем, 100).

Решение, которое пришло мне в голову, состояло в том, чтобы 1. отсортировать его с помощью быстрой сортировки2. получить топ 10.

Но есть ли лучшая альтернатива?

Answer 1

Меня попросили тот же алгоритм на собеседовании.Я сделал это, если кто-то может сравнить это с самым быстрым алгоритмом в Java - будет очень полезно.

    public int[] findTopNValues(int[] anyOldOrderValues, int n) {
        if (n < 0) {
            return new int[]{};
        }
        if (n == 1) {
            return new int[]{findMaxValue(anyOldOrderValues)};
        }

        int[] result = new int[n + 1];
        for (int i = 0; i < Math.min(n, anyOldOrderValues.length); i++) {
            result[i] = anyOldOrderValues[i];
        }
        Arrays.sort(result);

        int max = result[0];
        for (int i = n - 1; i < anyOldOrderValues.length; i++) {
            int value = anyOldOrderValues[i];
            if (max < value) {
                result[n] = value;
                Arrays.sort(result);
                int[] result1 = new int[n + 1];
                System.arraycopy(result, 1, result1, 0, n);
                result = result1;
                max = result[0];
            }
        }
        return convertAndFlip(result, n);
    }

    public static int[] convertAndFlip(int[] integers, int n) {
        int[] result = new int[n];
        int j = 0;
        for (int i = n - 1; i > -1; i--) {
            result[j++] = integers[i];
        }
        return result;
    }

и тест для этого:

public void testFindTopNValues() throws Exception {
    final int N = 100000000;
    final int MAX_VALUE = 100000000;
    final int returnArray = 1000;
    final int repeatTimes = 5;

    FindTopValuesArraySorting arraySorting = new FindTopValuesArraySorting();

    int[] randomArray = createRandomArray(N, MAX_VALUE);
    for (int i = 0; i < repeatTimes; i++) {

        long start = System.currentTimeMillis();
        int[] topNValues = arraySorting.findTopNValues(randomArray, returnArray);
        long stop = System.currentTimeMillis();

        System.out.println("findTopNValues() from " + N + " elements, where MAX value=" + (MAX_VALUE - 1) + " and return array size " + returnArray + " elements : " + (stop - start) + "msec");
        // System.out.println("Result list = " + Arrays.toString(topNValues));
    }
}

private static int[] createRandomArray(int n, int maxValue) {
    Random r = new Random();
    int[] arr = new int[n];
    for (int i = 0; i < n; i++) {
        arr[i] = r.nextInt(maxValue);
    }
    return arr;
}

Результат примерно такой:

findTopNValues() from 100000000 elements, where MAX value=99999999 and return array size 1000 elements : 395msec
findTopNValues() from 100000000 elements, where MAX value=99999999 and return array size 1000 elements : 311msec
findTopNValues() from 100000000 elements, where MAX value=99999999 and return array size 1000 elements : 473msec
findTopNValues() from 100000000 elements, where MAX value=99999999 and return array size 1000 elements : 380msec
findTopNValues() from 100000000 elements, where MAX value=99999999 and return array size 1000 elements : 406msec

~ 400 мсек среднего результата, для получения 1000 макс. Целых чисел из массива 100.000.000 исходных элементов.неплохо!

Только что попробовал установить сверху:

findTopNValues() from 101 elements and return array size 10 elements : 1msec
Result list = [998, 986, 986, 986, 947, 944, 926, 924, 921, 902]
Original list = [403, 459, 646, 467, 120, 346, 430, 247, 68, 312, 701, 304, 707, 443, 753, 433, 986, 921, 513, 634, 861, 741, 482, 794, 679, 409, 145, 93, 512, 947, 19, 9, 385, 208, 795, 742, 851, 638, 924, 637, 638, 141, 382, 89, 998, 713, 210, 732, 784, 67, 273, 628, 187, 902, 42, 25, 747, 471, 686, 504, 255, 74, 638, 610, 227, 892, 156, 86, 48, 133, 63, 234, 639, 899, 815, 986, 750, 177, 413, 581, 899, 494, 292, 359, 60, 106, 944, 926, 257, 370, 310, 726, 393, 800, 986, 827, 856, 835, 66, 183, 901]

Answer 2

Да, есть способ сделать лучше, чем быстрая сортировка. Как указал Инь Чжу, вы можете сначала найти k-й по величине элемент, а затем использовать это значение элемента в качестве своей оси, чтобы разделить массив