g732 - 110北二3.尋找中位數

🔗 前往 ZeroJudge 原題

題目描述

題目要求找出給定數列的中位數。輸入包含一個整數 n，代表數列的長度，接下來 n 個整數，代表數列中的元素。由於數列中的元素範圍有限 (0 到 500)，可以使用計數排序的方法來有效地找到中位數。

解題思路

此題使用計數排序的概念。首先，建立一個大小為 501 的陣列 a，用於儲存每個數字出現的次數。遍歷輸入的數列，將每個數字對應的 a 陣列中的元素加 1。然後，從 a 陣列的索引 0 開始，累加每個索引的元素值，直到累加值大於或等於 n/2 + 1。此時，對應的索引值即為數列的中位數。

複雜度分析

• 時間複雜度: O(n + k)，其中 n 是輸入數列的長度，k 是數列中最大值的範圍 (在本題中 k=500)。
• 空間複雜度: O(k)，因為需要一個大小為 k+1 的陣列來儲存計數。

程式碼

#include <iostream>
using namespace std;
int a[505],k,n;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> n;
	for(int i=0;i<n;++i){
		cin >> k;
		a[k]++;
	}
	n=n/2+1;
	for(int i=0;i<=500;++i){
		n-=a[i];
		if(n<=0){
			cout << i ;
			break;
		}
	}
}