寻找整型数组中第N大的数字的最快方法是什么？

Question

我希望能够在C#中找到一个更快的函数来查找整数数组中第N大的数字。这个函数需要输入N和数组，返回该数字的索引。

这是我已经有的代码。它仅仅对数组进行排序，然后返回那个数字的索引。尽管它可以完美地工作，但我不确定是否这是最快的方法。似乎有一种算法可以避免完全排序。

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)

- Moradnejad

---

http://stackoverflow.com/questions/11393019/finding-nth-largest-number-many-times-when-the-array-size-is-increasing?rq=1 - Fᴀʀʜᴀɴ Aɴᴀᴍ

为什么你要编写自己的排序算法？如果你想了解它，那没问题，但冒泡排序并不是最快的。如果你不想麻烦地编写自己的快速排序实现，也可以使用 Array.Sort。 - Daan Wilmer

你的排序是n²，很明显不是最快的。 - njzk2

@FᴀʀʜᴀɴAɴᴀᴍ，抱歉问个题外话，但您是如何将您的名字设置成这样的呢？我该如何设置我的名字呢？ - Tᴀʀᴇǫ Mᴀʜᴍᴏᴏᴅ

@TaReQMahMooD 说实话，我也为了那个东西搜索了很多（相信我）。我发现它被称为小型大写字母。 -> Tᴀʀᴇǫ Mᴀʜᴍᴏᴏᴅ - Fᴀʀʜᴀɴ Aɴᴀᴍ

Answer 1

随机快速选择算法的平均时间复杂度为O(n)。在实践中很少出现O(n^2)的情况。它使用了快速排序的分区函数。

- Neda Sharifi

---

QuickSelect on Wikipedia，以及C#实现示例。 - Matthew Watson

但它的最坏情况性能为n^2，尽管我不太明白k是被视为常数还是n。 - njzk2

Answer 2

如果您的数组有数千个数字，并且您需要第五大的数字，那么您会排序许多不需要的数字。

保持长度为n的升序排序序列（链表？）是否更快，并针对每个元素检查它是否大于第一个元素（在升序中是最小的）？

如果较小：跳到大数组中的下一个元素 如果较大：从已排序数组中删除最小的元素，这是第一个元素，并将较大的元素插入适当的位置，保持数组排序。 扫描完整个数组后，您排序后的序列中的第一个元素就是您要查找的元素。

大多数比较仅与已排序数组的第一个元素进行。您将不得不N次更改数组，一次是为了N个最大的数字。更改数组是删除第一个元素（最小值）并找到插入新元素以保持数组排序的位置。

更正：我的说法数组必须更改N次是不正确的。可以最容易地看到这一点，即当提供按升序排序的数组时：每个比较的数字都将大于N大小数组中最小的数字，从而导致替换。

- Harald Coppoolse

---

我想指出，使用排序链表有些过度。一个大小为N的最小堆（堆顶元素比其他所有元素都小）足以选择N个最大的元素，它的堆顶是第N大的元素，完全回答了问题。即使你想在最后将N个最大的元素排序，也最好在选择它们时使用最小堆，因为通常情况下堆需要的维护比排序列表少。 - Matthieu M.

这也是我想到的第一个算法，运行时间为O(n * N) - 对于数组中的每个元素，你需要与N个元素比较，以确定是否应该在您的shortlist上。如果N很小（或者对于快速选择运气不佳），那么使用它可能更好，但对于较大的N，我猜快速选择会更快。 - Daan Wilmer

@MatthieuM提出的使用最小堆的建议使时间复杂度降至O(n log(N))。 - Pepe Mandioca

Daan说：“你必须与N个元素进行比较，看看它是否应该出现在你的短列表中。”为什么？如果数组已经排序，我只需要与第一个元素进行比较，是吗？ - Harald Coppoolse

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。

- Domysee

---

通过跟踪索引，您可能可以在一次遍历中完成这个操作。 - user2697817

后处理方法在短列表中存在非唯一条目的情况下也存在问题。保留索引开销最小。 - Keith

这种方法在数组包含重复值的情况下无法正常工作。 - Mateen Ulhaq

@user2697817 感谢你的提示。抱歉这么晚才更新答案。 - Domysee

@MateenUlhaq 是的，我选择忽略重复值是可能存在的事实，因为我不知道它应该如何处理。它应该将重复值视为一个，还是仍然将它们视为多个？ - Domysee

@Keith 你说得对，跟踪索引实际上使代码更加简洁。 - Domysee

Answer 4

you need to use Selection algorithm https://en.wikipedia.org/wiki/Selection_algorithm

here nice slides: https://c3p0demo.googlecode.com/svn/trunk/scalaDemo/script/Order_statistics.ppt generally algorithm:

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)

- kain64b

Answer 5

您可以创建一个大小为N的堆，其中最大的数字作为其第一个元素（与通常给出的最小数字相反）。然后遍历整个整数数组，在您有一个小于堆中最大成员的元素时，将其插入到堆中。如果这使堆的大小超过N，则删除其中最大的成员。这应该是最便宜的方法之一。特定的“第m大的n”算法可能会胜过它，但在渐近意义下可能不会。

- user5704517

Answer 6

您的排序算法远不是最快的。您应该搜索“ 快速排序 ”以获得更快的算法。

在您实现了快速排序后，您可以考虑是否真的需要对整个数组进行排序。假设您想找到 10,000 个数字中的前 20 个最大值，为什么要对其余的 9,980 个数字进行排序呢？您可以轻松修改快速排序算法，使其找到 N 个最大的数字，但大部分情况下忽略其余数字。

- gnasher729

Answer 7

也许这会对某些人有所帮助。在整数数组中找到第n大的数字。

            int[] arr = new int[] { 3, 2, 1, 5 };
            Array.Sort(arr);
            int elemCount = 0;
            int? thirdLargestNumber = null;
            foreach (var elem in arr)
            {
                var temp = arr.Skip(elemCount).ToArray();
                if (temp.Length == 3) //replace `3` with variable.
                { 
                    thirdLargestNumber = temp[0];
                    break;
                }
                elemCount++;
            }
            Console.WriteLine($"Third largest number = {thirdLargestNumber}");

- Hamza Iftikhar

Answer 8

我尝试使用C#中的Linq来完成它。在Linq中，OrderBy()和OrderByDescending()排序使用平均时间复杂度为O(N*logN)的快速排序算法。

private static List<int> GetNthLargestNumber(List<int> integerList, int nThPosition)
{       
    // Write your logic here.
    var largestNumbers = integerList
        .Select((v,i) => new { Index = i, Value = v })
        .GroupBy(s=>s.Value)
        .OrderByDescending(s=>s.Key) // uses Quick sort with O(N*logN) average time complexity.
        .Skip(nThPosition - 1)
        .First()
        .ToList();
    
    foreach(var n in largestNumbers)
    {
        Console.WriteLine($"{n.Index}->{n.Value}" );
    }
    
    var largestNumberIndexes = largestNumbers.Select(s=> s.Index).ToList();
    
    return largestNumberIndexes;
}

我在https://dotnetfiddle.net/Rz8r6A上有一个完整的工作程序。

- S.Mishra