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

Given [4, 5, 1, 2, 3], return 3.

Given [7, 9, 4, 5], return 5.

思路：1.排序，找到其Median，时间复杂度为 O(nlogn).

　　　2.找从小到大的第K个数，找median则转换为找从小到大的 nums.length / 2 (当 nums.length 为偶数时） 或 nums.length / 2 + 1 （当nums.length 为奇数时). 时间复杂度为O(n).

 　     找从小到大第K个数的关键是 快速排序的核心 partition.

相关题目：Kth Largest Element in an Array （从大到小的第K个数）

1 public class Solution { 2     /** 3      * @param nums: A list of integers. 4      * @return: An integer denotes the middle number of the array. 5      */ 6     public int median(int[] nums) { 7         if (nums == null || nums.length == 0) { 8             return -1; 9         }10         if (nums.length % 2 == 0) {11             return findKth(nums, 0, nums.length - 1, nums.length / 2);12         } else {13             return findKth(nums, 0, nums.length - 1, nums.length / 2 + 1);14         }15         16     }17     18     private int findKth(int[] nums, int left, int right, int k) {19         if (left == right) {20             return nums[left];21         }22         int position = partition(nums, left, right);23         if (position + 1 == k) {24             return nums[position];25         } else if (position + 1 > k) {26             return findKth(nums, left, position - 1, k);27         } else {28             return findKth(nums, position + 1, right, k);29         }30     }31     32     private int partition(int[] nums, int left, int right) {33         int pivote = nums[left];34         while (left < right) {35             while (left < right && nums[right] >= pivote) {36                 --right;37             }38             nums[left] = nums[right];39             while (left < right && nums[left] <= pivote) {40                 ++left;41             }42             nums[right] = nums[left];43         }44         nums[left] = pivote;45         return left;46     }47 }