给定一个未排序的整数数组，找到其中位数。
中位数是排序后数组的中间值，如果数组的个数是偶数个，则返回排序后数组的第N/2个数。
您在真实的面试中是否遇到过这个题？ Yes 哪家公司问你的这个题？ Airbnb Alibaba Amazon Apple Baidu Bloomberg Cisco Dropbox Ebay Facebook Google Hulu Intel Linkedin Microsoft NetEase Nvidia Oracle Pinterest Snapchat Tencent Twitter Uber Xiaomi Yahoo Yelp Zenefits 感谢您的反馈 样例
给出数组[4, 5, 1, 2, 3]， 返回 3
给出数组[7, 9, 4, 5]，返回 5
挑战
时间复杂度为O(n)
标签 Expand LintCode 版权所有 快速排序 数组
相关题目 Expand
- 3 (lintcode-copyright),(heap),(priority-queue) 困难 中位数 II 24 % 3 (sorted-array),(divide-and-conquer),(array) 困难 两个排序数组的中位数 20 %
-
public class Solution {
public int median(int[] nums) {
// write your code here
if(nums.length==1){
return nums[0];
}
nums = quicksort(nums, 0, nums.length-1);
if(nums.length%2==0){
return nums[nums.length/2-1];
}
return nums[nums.length/2];
}
public static int[] quicksort(int[] array,int l,int h){
int low = l+1;
int high = h;
if(low>high) return null ;
int key = array[l];
while(true){
while(low<high&&array[low]<key){
low++;
}
while(array[high]>key){
high--;
}
if(low>=high) break;
//交换2者的值
int temp = array[low];
array[low] = array[high];
array[high] = temp;
if(array[low]==key){
high--;
}else{
low++;
}
}
array[l] = array[high];
array[high] = key;
if(l<high-1) quicksort(array, l, high-1);
if(h>high+1) quicksort(array, high+1,h );
return array;
}
}