Wednesday, July 1, 2015

Median

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.
Have you met this question in a real interview? 
Yes
Example
Given [4, 5, 1, 2, 3], return 3
Given [7, 9, 4, 5], return 5

Challenge
O(n) time.

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
        return quickSort(nums, 0, nums.length-1, (nums.length+1)/2);
    }
    
    private int quickSort(int[] nums, int i, int j, int k){
        int start = i++;
        while(i<=j){
            while(i <= j && nums[i] < nums[start]) i++;
            while(i <= j && nums[j] >= nums[start]) j--;
            if(i < j)
            swap(nums, i, j);
        }
        swap(nums, start, j);
        if(k == j + 1) return nums[j];
       
        else if(k > j + 1) return quickSort(nums, j+1, nums.length-1, k);
        else {
            return quickSort(nums, 0, j-1, k);
        }
    }
    private void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

No comments:

Post a Comment