给定一个未排序的整数数组，找到其中位数。
中位数是排序后数组的中间值，如果数组的个数是偶数个，则返回排序后数组的第N/2个数。
样例
给出数组[4, 5, 1, 2, 3]， 返回 3
给出数组[7, 9, 4, 5]，返回 5
快速排序的思想，我只需要排一边就可以，可以接近O(n)的复杂度。
public class Solution080 {
/**
* @param nums: A list of integers
* @return: An integer denotes the middle number of the array
*/
public static void main(String[] args) {
int[] nums = {4,5,1,2,3,3};
int result = median(nums);
System.out.println(result);
}
public static int median(int[] nums) {
if (nums.length == 1){
return nums[0];
}
return sub(nums, 0, nums.length-1, (nums.length-1)/2);
}
private static int sub(int[] nums, int start, int end, int size) {
int p = partition(nums, start, end);
if (p == size) {
return nums[p];
}else if (p > size){
return sub(nums, start, p - 1, size);
}else{
return sub(nums, p + 1, end, size);
}
}
private static int partition(int[] nums, int start, int end) {
int pivot = nums[end];
int j = start;
for (int i = start; i < end; i++) {
if (nums[i] < pivot) {
exch(nums, i, j);
j++;
}
}
exch(nums, j, end);
return j-1;
}
private static void exch(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
