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 < array.Length; ++i)
            {
                int n = array[i];
                if (n > 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 < 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];
        }

說明

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

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

文章標籤
創作者介紹

小殘的程式光廊

emn178 發表在 痞客邦 PIXNET 留言(0) 人氣()