本文准备讲解1个简单的算法编程问题, 这个算法编程问题来自LintCode平台。不了解.LintCode平台的读者可以阅读笔者文章(在线编程平台推荐-LeetCode)。问题的英文版本描述如下:
Median
Given an unsorted array with integers, find the median of it.
A median is the middle number of the array after it is sorted.
If there are even numbers in the array, return the N/2-th number after sorted.
Example
Given [4, 5, 1, 2, 3], return 3.
Given [7, 9, 4, 5], return 5.
中位数
给定一个未排序的整数数组,找到其中位数。
如果数组的元素个数是偶数,则返回排序后数组的第N/2个数。
样例
给出数组[4, 5, 1, 2, 3], 返回 3
给出数组[7, 9, 4, 5],返回 5
该问题要求先对整数数组做排序处理,然后找到整数序列的中位数。所以核心问题只有1个:如何对整数数组排序处理。现在公布1种简单的算法方案。