Каков самый быстрый способ найти N-е наибольшее количество массива INT?

Я хочу, чтобы более быстрая функция находила N-е наибольшее количество массива Int в С#. Эта функция принимает N и Array и возвращает индекс этого числа.

Вот что у меня уже есть. Он просто сортирует массив и затем возвращает индекс этого числа. Он отлично работает, но я не уверен, что это самый быстрый способ. логичным представляется алгоритм без полной сортировки.

static int myFunction(int[] array, int N){
    int[] indexes = new int[array.Length];
    for (int i = 0; i < indexes.Length; i++)
        indexes[i] = i;

    for (int i = 0; i < array.Length; i++)
    {
        for (int j = i + 1; j < array.Length; j++)
        {
            if (array[i] < array[j])
            {
                int m = array[j];
                array[j] = array[i];
                array[i] = m;

                m = indexes[j];
                indexes[j] = indexes[i];
                indexes[i] = m;
            }
        }
    }
    return indexes[N];
}

некоторые результаты:

myFunction(new int[] { 1, 3, 2, 0, 10 }, 0); //returns 4 (index of 10)
myFunction(new int[] { 1, 3, 2, 0, 10 }, 1); //returns 1 (index of 3)
myFunction(new int[] { 1, 3, 2, 0, 10 }, 2); //returns 2 (index of 2)

Ответ 1

Рандомизированный алгоритм быстрого выбора работает в средней сложности О (n). Практически очень редко бывает O (n ^ 2). Он использует функцию быстрой сортировки

Ответ 2

Если ваш массив имеет размер в миллион чисел, и вам нужно пятое по величине число, то вы сортируете много чисел, которые вам не понадобятся.

Не было бы быстрее сохранить восходящую упорядоченную последовательность длины n (связанный список?), и для каждого элемента проверьте, больше ли он первого (который является наименьшим в порядке возрастания

Если меньше: перейдите к следующему элементу в вашем большом массиве
Если больше: удалите наименьший из отсортированного массива, который является первым элементом и вставьте более крупный элемент в нужное место, сохраните массив отсортированным.

После сканирования вашего полного массива первым элементом вашей упорядоченной последовательности является тот, который вы ищете.

Большинство сравнений относятся только к первому элементу вашего отсортированного массива. Вам придется изменить массив N раз, один раз для N наибольших чисел. Изменение массива состоит в том, чтобы удалить первый элемент (самый маленький) и найти место, где нужно вставить новый элемент, чтобы отсортировать массив

Исправление: мое утверждение о том, что массив должен быть изменен, N-время неверно. Это можно увидеть наиболее легко, предлагая массив, отсортированный по возрастанию: каждый сравниваемый номер будет больше, чем самый маленький в массиве N-размера, и, таким образом, заменит

Ответ 3

Это будет реализация ответа @HaraldDutch.

int get(int[] array, int n)
{
    var comparer = Comparer<int>.Create((x, y) => array[x].CompareTo(array[y]));    //compare the array entries, not the indices
    var highestIndices = new SortedSet<int>(comparer);
    for (var i = 0; i < array.Length; i++)
    {
        var entry = array[i];
        if (highestIndices.Count < n) highestIndices.Add(i);
        else if (array[highestIndices.Min] < entry)
        {
            highestIndices.Remove(highestIndices.Min);
            highestIndices.Add(i);
        }
    }

    return highestIndices.Min;
}

Вам нужно было бы передать 1 вместо 0.

Ответ 4

вам нужно использовать алгоритм выбора https://en.wikipedia.org/wiki/Selection_algorithm

здесь приятные слайды: https://c3p0demo.googlecode.com/svn/trunk/scalaDemo/script/Order_statistics.ppt обычно алгоритм:

Select(A,n,i):
    Divide input into ⌈n/5⌉ groups of size 5.

    /* Partition on median-of-medians */
    medians = array of each group’s median.
    pivot = Select(medians, ⌈n/5⌉, ⌈n/10⌉)
    Left Array L and Right Array G = partition(A, pivot)

    /* Find ith element in L, pivot, or G */
    k = |L| + 1
    If i = k, return pivot
    If i < k, return Select(L, k-1, i)
    If i > k, return Select(G, n-k, i-k)

Ответ 5

Вы можете создать кучу размера N, которая имеет наибольшее число в качестве своего первого элемента (в отличие от самого маленького, обычно заданного). Затем вы проходите через массив целых чисел, и всякий раз, когда у вас есть элемент, меньший, чем самый большой член кучи, вы вставляете его в кучу. Если это делает кучу превышением размера N, вы удаляете в ней наибольший член.

Это должно быть одним из самых дешевых способов сделать это. Конкретные "nth most of m" алгоритмы могут избить его, но, вероятно, не асимптотически.

Ответ 6

Ваш алгоритм сортировки далеко не самый быстрый. Вы должны google для "Quicksort" для гораздо более быстрого алгоритма.

И после того, как вы внедрили Quicksort, вы подумали, действительно ли вам нужно отсортировать полный массив. Скажите, что вы хотите найти 20 крупнейших из 10 000 номеров, почему бы вам отсортировать оставшиеся 9 980 номеров? Вы можете легко модифицировать QuickSort, чтобы найти N наибольших номеров, но в основном игнорировать остальные.