- 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
Example 1:
Input：[4, 5, 1, 2, 3]
Output：3
Explanation:
After sorting，[1,2,3,4,5]，the middle number is 3
Example 2:
Input：[7, 9, 4, 5]
Output：5
Explanation:
After sorting，[4,5,7,9]，the second(4/2) number is 5
Challenge
O(n) time.
Notice
The size of array is not exceed 10000
解法1：quickSelect。时间复杂度O(n)。
注意quickSelect里面当start>=end时是return nums[start]而不是nums[k]。
代码如下:
class Solution {
public:
/**
* @param nums: A list of integers
* @return: An integer denotes the middle number of the array
*/
int median(vector<int> &nums) {
int n = nums.size();
vector<int> orignums;
//int index = (n & 0x1) ? n / 2 + 1 : n / 2;
return quickSelect(nums, 0, n - 1, (n + 1) / 2);
return 0;
}
private:
int quickSelect(vector<int> &nums, int start, int end, int k) {
if (start >= end) return nums[start]; //nums[k];
int left = start, right = end;
int pivot = nums[left + (right - left) / 2];
while (left <= right) {
while (left <= right && nums[left] < pivot) left++;
while (left <= right && nums[right] > pivot) right--;
if (left <= right) {
swap(nums[left], nums[right]);
left++;
right--;
}
}
if (start + k - 1 <= right)
return quickSelect(nums, start, right, k);
if (start + k - 1 >= left)
return quickSelect(nums, left, end, k - (left - start));
return pivot;
}
};
解法2：MaxHeap
TBD
代码同步在
https://github.com/luqian2017/Algorithm