中位数

给定一个未排序的整数数组，找到其中位数。

中位数是排序后数组的中间值，如果数组的个数是偶数个，则返回排序后数组的第N/2个数。

给出数组[4, 5, 1, 2, 3]，返回 3

给出数组[7, 9, 4, 5]，返回 5

挑战

时间复杂度为O(n);

主要利用快排递归划分的思想，可以在期望复杂度为O(n)的条件下求第k大数。快排的期望复杂度为O(nlogn)，因为快排会递归处理划分的两边，而求第k大数则只需要处理划分的一边，其期望复杂度将是O(n)。详细的证明见《算法导论》。

当然在经过前面几道题的洗礼以后，妹纸我果断用了C++来写。

 1 class Solution {
 2 public:
 3     /**
 4      * @param nums: A list of integers.
 5      * @return: An integer denotes the middle number of the array.
 6      */
 7     int median(vector<int> &nums) {
 8         // write your code here
 9         sort(nums.begin(),nums.end());
10         int n=nums.size();
11         if(n%2==0) {
12             return nums[n/2-1];
13         }else{
14             return nums[(n-1)/2];
15         }
16     }
17 };

还是非常简单的一道题