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

文章已搬家，請點擊前往👈

REDIRECT_MODE = 1;

How to find second largest number in array.

How to find kth largest number in array.

其實這是兩種不同題目，不過由於有些類似，就放在一起講了。

首先先看找第二大的方法。

解法

這邊使用C#來實作

static int Find(int[] array) { int max = int.MinValue; int second = int.MinValue; for (int i = 0; i max) { second = max; max = n; } else if (n > second) second = n; } return second; }

說明

找最大的方法我們都會，很簡單地用一個變數去保存目前最大，那找第二大不就可以很簡單的用兩個變數去保存？反之找最小的想法也是一樣，就不在此贅述；這個方法時間複雜度為O(N)。

找第K大的方法

解法

static int Find(int[] array, int k) { List list = new List(); for (int i = 0; i list[j]) break; if (j

說明

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

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

-->

小殘的程式光廊

提供一些演算法、資料結構、程式題目的整理與說明，PHP和JavaScript的基本教學和一些程式相關問題與解法。

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

參觀人氣

熱門文章

文章分類

電腦程式 (10)

最新文章

文章搜尋

文章精選