[UVA]What is the Median?

UVA 10107、CPE  10527 程式解題。

解題觀念 :


這題很簡單（雖然是二星題）。就是要求中位數，也就是說需要用到排序。

每輸入一個數字，就要將其插入陣列裡面。

所以不是一次輸入完畢哦！是要逐次輸入，逐次插入。

還有如果項數只有一項時，也要印出。



解題步驟：

宣告ArrayList 物件 array，用來存放數字，也方便等下直接用sort()排序。

宣告整數 n ，輸入數字；宣告整數 median，存放中位數。

將每次所輸入的數字 n ，用array.add(n) ，將 n 存入array裡面。

先判斷array大小是否為一，如果是，則直接印出。
(因為題目要求，即使只有一個數字也要印出中位數。)

如果否，則進入else。

在計算中位數之前，要記得先做排序 Collections.sort()。
(小K原本是用 Arrays.sort() 做排序，但不知道為什麼卻一直逾時......後來改用Collection呼叫就Accept了。 其速度差的原因有待查詢。)

至於為甚麼可以用Collection呼叫，請參考這張圖。

如果看了圖還是不知道為什麼，表示你Java基礎知識還不夠，資料結構要加強喔!

判斷array項數為奇數還是偶數。(因為奇、偶數求中位數的方法不一樣，對吧?!)

再來就是用array.get() ，取出array裡面指定位置的值，做計算。

至於求中位數的方法，大家在小學或國中都有學過，所以演算法部份我就不說明了。
 (或是看EX的step by step 解說。)

最後，記得median要重新初始化。


EX :

1
3
4
60
70
50
2

n = 1 => array.add(1)。 //[1]

if(array.size()==1) => 符合；直接印出1。

n = 3 => array.add(3)。 //[1,3]

if(array.size()==1) => 不符合；進入else。

先做排序動作 => Collection.sort()，[1.3]。

判斷size為奇數項還是偶數項 => 為偶數項；if(array.size()%2==0)，符合。

宣告整數m1，儲存array.size()/2 -1那個位置的數值 = 1。

宣告整數m2，儲存array.size()/2那個位置的數值 = 3。

中位數 median = (m1 + m2) /2 = (1+3) /2 = 2。

接下來繼續輸入。

n = 4 => array.add(4)。 //[1,3,4]

if(array.size()==1) => 不符合；進入else。

先做排序動作 => Collection.sort()，[1.3,4]。

判斷size為奇數項還是偶數項 => 為奇數項；else if(array.size()%2!=0)，符合。

直接印出中位數 array.size()/2，3/2 = 1.5，會直接取整數1，印出數列位置1的那個值 = 3。

(其他繼續以此類推)


By   小K