iT邦幫忙

0

[C#] LeetCode 4. Median of Two Sorted Arrays 淺談中位數

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
https://ithelp.ithome.com.tw/upload/images/20201109/20132436e6K9iQ1MNy.png

意旨找出中位數,在2個已經排序過的陣列裡面

我們來看看中位數的定義吧!

簡單定義:
一組資料的中位數是指將資料從小到大排序後,最中間的數。

詳細定義(可略):

中位數(Median)

關於英文名稱:
Medium 形容詞 (是形容中等的;中間的)
Median 名詞   (除了媒介之外,還有也有中間的意思)

https://ithelp.ithome.com.tw/upload/images/20201109/20132436WbojkexqI5.png
見解:
關於中位數值觀上來看就是最中間的數,
那生活上有甚麼應用呢?

    1.     最近沸沸揚揚的美國總統大選(民調)
    2.     計算全國人民的薪資水平
    3.     算同班學生成績
    
大多數人認知計算成績、薪資 往往都使用平均法↓↓↓

如 1,2,3,4,5 之平均數與中位數都是 3。
至於對 1,2,3,4,500,平均數為 102。
那一特別大的數 500,讓平均數增大不少,但中位數仍為 3,並不受 5 變成 500 之影響。

Q&A:
    哪種方法好呢?
    曾有學者指出 [統計只適合處理大量數據],試圖以此消弭一些統計所可能引起的爭議。
    但這講法並不正確,因即使很少量的數據,求平均數,也毫無問題。
    因此統計絕非只適合處理大量數據。而有些民調被認為結果不可靠,關鍵也並不在於樣本數的多寡。
    這樣說好了,以美國棒球大聯盟(MLB)球員的年薪來說,有報導說中位數是 470 萬美元。
    真的是這樣嗎?因實際收入可能包含績效獎金等,且薪水涉及隱私,記者掌握的資料不見得都很可靠
    由於原始數據便可能不精確,這時太在乎細節,就不是那麼必要。
    因此是否真有一個中間位置,是否真能前後各切一半,何須太在意?
    只要是一差不多在中間的值,讓人對球員年薪落在那裡,能略有概念就行了。

方向:
解答有很多種實現方法,而中位數會發現幾個特點:
* 中位數前面的數字與後面的數字一樣多(在偶數元素情況下或相差1)
* 若某個數字前後的數字數量相同(或相差1)則為該數列的中位數
* 刪除前N個元素與後N個元素後,中位數不變
* 從大陣列中按順序任意取走n-1組元素,與剩下的元素共構成n個子列,
每個子列存在中位數:m1,m1...mn,min,max分別為其中最小者與最大者,
則原數列的中位數m滿足:min<=m<=max

今天用較為簡單的方法處理
1.先將排序好的陣列合併(類似氣泡搜尋)
2.在判斷奇數或偶數
中位數會有兩種情況
* 當輸入陣列的個數是奇數時,就取最中間的那個;
* 當輸入的數目是偶數時,則要取最中間的那兩個加總除以二。
程式碼如下

public class Solution {
    public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
        var list1 = new  List<int>(nums1);
        var list2 = new  List<int> (nums2);

        var mergedList= list1.Concat(list2).ToList();

        mergedList.Sort();

        if(mergedList.Count() % 2 == 0)
        {
            int minIndex = mergedList.Count()/2;

            double i = (mergedList[minIndex-1] + mergedList[minIndex])/2.0 ;

            return i;
        }

        else
        {
            int minIndex = mergedList.Count()/2;            
            return mergedList[minIndex];
        }

        return 0;
    }
}

https://ithelp.ithome.com.tw/upload/images/20201109/20132436ElcRXaZbbk.jpg


尚未有邦友留言

立即登入留言