Median 80

Question

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.

Challenge

O(n) time.

Solution

用quicksort（或者其它排序法）排序后再找median。

没有找到O(n)的方法。

代码如下：

public class Solution {
    /**
     * @param nums: A list of integers.
     * @return: An integer denotes the middle number of the array.
     */
    public int median(int[] nums) {
        // write your code here
        quickSort(nums, 0, nums.length - 1);

        if(nums.length % 2 == 0){
            return nums[nums.length / 2 - 1];
        }

        return nums[nums.length / 2];
    }

    private void quickSort(int[] nums, int start, int end){
        if(start < end){
            int q = partition(nums, start, end);
            quickSort(nums, start, q - 1);
            quickSort(nums, q + 1, end);
        }
    }

    private int partition(int[] nums, int start, int end){
        int pivot = nums[end];
        int i = start - 1;
        for(int j = start; j < end; j++){
            if(nums[j] < pivot){
                i += 1;
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }
        int temp = nums[i + 1];
        nums[i + 1] = nums[end];
        nums[end] = temp;

        return i + 1;
    }
}