在陣列中找出第 K 大的數字

題目

在陣列中找出第 K 大的數字。
Find Kth largest number in an array.

說明

找第 K 大的數字，我們可以直覺的用排序後就可以找出來，時間複雜度取決於排序演算法，例如使用快速排序法為 O(n log n)。

另外一個方法是延續前一個題目的想法，找第 K 大就用 K 個變數去保存？不過由於 K 也是個變數，所以我們需利用動態的資料結構來保存，這個 Case 使用 Linked List 是最合適。時間複雜度則為 O(n K)，而當 K 很小的時候可以接近 O(n)的效能，反之，K 很大的時候，可能會比直接用快速排序法還慢。

解法

static int Find(int[] array, int k)
{
    List list = new List();
    for (int i = 0; i < array.Length; ++i)
    {
        int n = array[i];
        int j = 0;
        for (int length = Math.Min(list.Count, k); j < length; ++j)
            if (n > list[j])
                break;
        if (j < k)
            list.Insert(j, n);
    }
    return list[k - 1];
}