Description

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], return3.

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

Solution

1. O(nlogn)- partition
2. O(n)- two priority queue

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
        if (nums == null || nums.length == 0) {
            return 0;
        }

        return median(nums, 0, nums.length - 1);
    }

    private int median(int[] nums, int left, int right) {
        int partition = partition(nums, left, right);
        if (partition == (nums.length - 1) / 2) {
            return nums[partition];
        } else if (partition > (nums.length - 1) / 2) {
            return median(nums, left, partition - 1);
        } else {
            return median(nums, partition + 1, right);
        }
    }

    private int partition(int[] nums, int left, int right) {
        int pivot = nums[left];
        while (left < right) {
            while (left < right && nums[right] >= pivot) {
                right--;
            }

            nums[left] = nums[right];
            while (left < right && nums[left] <= pivot) {
                left++;
            }

            nums[right] = nums[left];
        }

        nums[left] = pivot;
        return left;
    }
}