|
4 | 4 |
|
5 | 5 | - lintcode: [(80) Median](http://www.lintcode.com/en/problem/median/) |
6 | 6 |
|
7 | | -``` |
| 7 | +### Problem Statement |
| 8 | + |
8 | 9 | Given a unsorted array with integers, find the median of it. |
9 | 10 |
|
10 | 11 | A median is the middle number of the array after it is sorted. |
11 | 12 |
|
12 | | -If there are even numbers in the array, return the N/2-th number after sorted. |
| 13 | +If there are even numbers in the array, return the `N/2`-th number after |
| 14 | +sorted. |
13 | 15 |
|
14 | | -Example |
15 | | -Given [4, 5, 1, 2, 3], return 3 |
| 16 | +#### Example |
16 | 17 |
|
17 | | -Given [7, 9, 4, 5], return 5 |
| 18 | +Given `[4, 5, 1, 2, 3]`, return `3`. |
18 | 19 |
|
19 | | -Challenge |
20 | | -O(n) time. |
21 | | -``` |
| 20 | +Given `[7, 9, 4, 5]`, return `5`. |
| 21 | + |
| 22 | +#### Challenge |
| 23 | + |
| 24 | +$$O(n)$$ time. |
22 | 25 |
|
23 | 26 | ## 题解 |
24 | 27 |
|
25 | 28 | 寻找未排序数组的中位数，简单粗暴的方法是先排序后输出中位数索引处的数，但是基于比较的排序算法的时间复杂度为 $$O(n \log n)$$, 不符合题目要求。线性时间复杂度的排序算法常见有计数排序、桶排序和基数排序，这三种排序方法的空间复杂度均较高，且依赖于输入数据特征（数据分布在有限的区间内），用在这里并不是比较好的解法。 |
26 | 29 |
|
27 | | -由于这里仅需要找出中位数，即找出数组中前半个长度的较大的数，不需要进行完整的排序，说到这你是不是想到了快速排序了呢？快排的核心思想就是以基准为界将原数组划分为左小右大两个部分，用在这十分合适。快排的实现见 [Quick Sort](http://algorithm.yuanbin.me/zh-hans/basics_sorting/quick_sort.html), 由于调用一次快排后基准元素的最终位置是知道的，故递归的终止条件即为当基准元素的位置(索引)满足中位数的条件时(左半部分长度为原数组长度一半)即返回最终结果。由于函数原型中左右最小索引并不总是原数组的最小最大，故需要引入相对位置(长度)也作为其中之一的参数。若左半部分长度偏大，则下一次递归排除右半部分，反之则排除左半部分。 |
| 30 | +由于这里仅需要找出中位数，即找出数组中前半个长度的较大的数，不需要进行完整的排序，说到这你是不是想到了快速排序了呢？快排的核心思想就是以基准为界将原数组划分为左小右大两个部分，用在这十分合适。快排的实现见 [Quick Sort](../basics_sorting/quick_sort.html), 由于调用一次快排后基准元素的最终位置是知道的，故递归的终止条件即为当基准元素的位置(索引)满足中位数的条件时(左半部分长度为原数组长度一半)即返回最终结果。由于函数原型中左右最小索引并不总是原数组的最小最大，故需要引入相对位置(长度)也作为其中之一的参数。若左半部分长度偏大，则下一次递归排除右半部分，反之则排除左半部分。 |
28 | 31 |
|
29 | 32 | ### Python |
30 | 33 |
|
@@ -156,6 +159,18 @@ public class Solution { |
156 | 159 |
|
157 | 160 | 以题目中给出的样例进行分析，`size` 传入的值可为`(len(nums) + 1) / 2`, 终止条件为`m - l + 1 == size`, 含义为基准元素到索引为`l`的元素之间(左半部分)的长度(含)与`(len(nums) + 1) / 2`相等。若`m - l + 1 > size`, 即左半部分长度偏大，此时递归终止条件并未变化，因为`l`的值在下一次递归调用时并未改变，所以仍保持为`size`; 若`m - l + 1 < size`, 左半部分长度偏小，下一次递归调用右半部分，由于此时左半部分的索引值已变化，故`size`应改为下一次在右半部分数组中的终止条件`size - (m - l + 1)`, 含义为原长度`size`减去左半部分数组的长度`m - l + 1`. |
158 | 161 |
|
| 162 | +P.S. 经 @l1xiao 提醒，也可直接将 size 固定，代码上更为简洁，置于个中缘由读者可先自行分析。 |
| 163 | + |
| 164 | +``` |
| 165 | + if (m + 1 == size) { |
| 166 | + return nums[m]; |
| 167 | + } else if (m + 1 > size) { |
| 168 | + return helper(nums, start, m - 1, size); |
| 169 | + } else { |
| 170 | + return helper(nums, m + 1, end, size); |
| 171 | + } |
| 172 | +``` |
| 173 | + |
159 | 174 | ### 复杂度分析 |
160 | 175 |
|
161 | 176 | 和快排类似，这里也有最好情况与最坏情况，平均情况下，索引`m`每次都处于中央位置，即每次递归后需要遍历的数组元素个数减半，故总的时间复杂度为 $$O(n (1 + 1/2 + 1/4 + ...)) = O(2n)$$, 最坏情况下为平方。使用了临时变量，空间复杂度为 $$O(1)$$, 满足题目要求。 |
0 commit comments