给定一个未排序的整数数组，找到其中位数。
中位数是排序后数组的中间值，如果数组的个数是偶数个，则返回排序后数组的第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 };
还是非常简单的一道题
原文：http://www.cnblogs.com/wangnanabuaa/p/4987207.html