[Java] UVa 10107 What is the Median?

題目連結

題意:
只有一組測資
每行輸入一個數字，形成越來越長的數列
每輸入一個數，就要輸出當前數列的中位數(排序後)
當數列長度為奇數，如5，輸出第3個數字
當數列長度為偶數，如6，輸出中間2數的平均，即第3, 4個的平均
當數字不為整數，輸出其整數部分
數字小於10000個，數字大小可能達2^31-1

解法:
如果每次輸入新的數就重新排列再找中位數，一定TLE
因此，必須在輸入時就按小到大的順序，將其放到合適位置
再將該 index 後面的元素都後移一位，可大幅縮短時間

如下，新增 5 之後
5 會從 1 開始比，直到發現比 6 小
5 擺在 6 的位置，6 ~ 9 往後移一位

然後，再從新數列找中位數即可

程式(Java):

	import java.util.*;
	public class Main {
	public static void main(String args[]) {
	Scanner sc = new Scanner(System.in);
	int arr[] = new int[10001];
	int count = 1;
	while (sc.hasNext()) {
	arr[count] = sc.nextInt();
	for (int i = 1; i < count; i++)
	if (arr[count] <= arr[i]) {
	int tmp = arr[i];
	arr[i] = arr[count];
	for (int j = i; j < count; j++) {
	int tmp2 = arr[j+1];
	arr[j+1] = tmp;
	tmp = tmp2;
	}
	break;
	}
	if (count % 2 == 1)
	System.out.println(arr[count/2 + 1]);
	else {
	long a = arr[count/2];
	long b = arr[count/2 + 1];
	System.out.println((a + b)/2);
	}
	count++;
	}
	}
	}

view raw UVa10107.java hosted with ❤ by GitHub