80 中位数

原题网址：http://www.lintcode.com/zh-cn/problem/median/

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

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

您在真实的面试中是否遇到过这个题？

Yes

样例

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

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

挑战

时间复杂度为O(n)

标签

 1 #include <iostream>
 2 #include <vector>
 3 #include <math.h>
 4 #include <string>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 int median(vector<int> &nums) {
 9 
10     int size=nums.size();
11 
12     sort(nums.begin(),nums.end());
13 
14     int index=0;
15     if (size%2==0)
16     {
17         index=size/2-1;
18     }
19     else
20     {
21         index=size/2;
22     }
23 
24     return nums[index];
25 }