找到第N个最大数量的INT数组的最快方法是什么？

Question

我想要一个更快的函数来在C#中找到第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)

Answer 1

随机快速选择算法适用于平均情况复杂度O(n).实际上,很少有O(n ^ 2).它使用quicksort的分区功能

Answer 2

如果你的阵列有一个数字大小,你需要第五大数字,那么你正在排序许多你不需要的数字.

保持长度为n的升序排序序列(链表？)并不是更快,并检查每个元素是否大于第一个(升序中最小的)

• 如果更小:跳到大型数组中的下一个元素
• 如果更大:从排序数组中删除最小的一个,这是第一个元素,并将较大的元素插入适当的位置,保持数组排序.

扫描完整数组后,排序序列中的第一个元素就是您要查找的元素.

大多数比较仅与排序数组的第一个元素有关.你必须N次更改数组,N次最大数字一次.更改数组是删除第一个元素(最小的)并找到插入新元素的位置以保持数组排序

更正:我声明数组必须更改N次是不正确的.当提供按升序排序的数组时,最容易看到这一点:每个比较的数字将大于N-size数组中的最小数字,从而导致替换

Answer 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.

Answer 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)

Answer 5

您可以创建一个大小为N的堆,其中第一个元素的编号最大(与通常给出的最小元素相对).然后,您将遍历整数数组,只要您的元素小于堆的最大成员,就可以将其插入堆中.如果这使得堆超过N的大小,则删除其中的最大成员.

这应该是最便宜的方法之一.特定的"第n个最大的m"算法可能会击败它,但可能不是渐近的.

Answer 6

您的排序算法到目前为止并不是最快的.你应该google for"Quicksort"获得更快,更快的算法.

在你实现了Quicksort之后,你会考虑是否真的需要对整个数组进行排序.假设您想要找到10,000个数字中最大的20个,为什么要对剩余的9,980个数字进行排序？您可以轻松修改Quicksort,以便找到N个最大的数字,但大部分时间忽略其余数字.