Median
Given a 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.
Challenge
O(n) time.
解题思路
最简单的方法是先对数组排序，然后取中位数。快排和归并排序等基于比较的排序算法的时间复杂度为O(logn)，桶排序、计数排序、基数排序等线性排序算法对数据有一定限制，且空间复杂度较高。
由于只需要找出中位数即可，所以可以参考快速排序中的 partition 操作，根据 pivot 元素将数组划分为左小右大的两部分，然后对包含中位数的部分继续查找即可。当 pivot 元素的下标等于数组长度的一半时，即为中位数。
易错点
- 一个数组的中位数位置
k = (length - 1)/2。
Java 实现
public
class
Solution
{
/**
*
@param
nums: A list of integers.
*
@return
: An integer denotes the middle number of the array.
*/
public
int
median
(
int
[] nums)
{
if
(nums ==
null
|| nums.length ==
0
) {
return
-
1
;
}
return
helper(nums,
0
, nums.length -
1
, (nums.length -
1
)/
2
);
}
private
int
helper
(
int
[] nums,
int
start,
int
end,
int
mid)
{
if
(start
>
= end) {
return
nums[end];
}
int
m = start;
for
(
int
i = start +
1
; i
<
end +
1
; i++) {
if
(nums[i]
<
nums[start]) {
m++;
swap(nums, i, m);
}
}
swap(nums, start, m);
if
(m == mid) {
return
nums[m];
}
else
if
(m
>
mid) {
return
helper(nums, start, m -
1
, mid);
}
else
{
return
helper(nums, m +
1
, end, mid);
}
}
private
void
swap
(
int
[] nums,
int
i,
int
j)
{
int
tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}