[HackerRank]尋找中位數(Find the Median)


題目描述

給定一個擁有奇數數量元素的陣列,你能夠在陣列整個排序好之前就找出它的中位數(中間值)嗎?

原題網址

https://www.hackerrank.com/challenges/find-the-median/

輸入格式

輸入第一行為一個整數n,且為奇數,範圍在1到1000001之間(包含1和1000001)。

第二行為n個用空格分隔的整數,範圍在-10000到10000之間(包含-10000和10000),不會重複。

輸出格式

輸出只會有一個整數,那就是這個陣列的中位數。

範例輸入

7
0 1 2 4 6 5 3

範例輸出

3

解題概念

參考這篇文章,學習快速選擇法:

https://magiclen.org/quickselect/

由於輸入的陣列元素皆不重複,因此中位數的元素索引位置即為陣列長度的一半。也就是說,利用快速選擇演算法,找出第「陣列長度一半」小的元素,就是題目要的輸出結果了。

參考答案

關於作者

Magic Len

Magic Len

各位好,我是Magic Len,是這網站的管理員。我是台灣台中大肚山上人,畢業於台中高工資訊科和台灣科技大學資訊工程系,曾在桃機航警局服役。我熱愛自然也熱愛科學,喜歡和別人分享自己的知識與經驗。如果你有興趣認識我,可以加我的Facebook,並且請註明是從MagicLen來的。

相關文章