Problem

Given a binary search tree and a new tree node, insert the node into the tree. You should keep the tree still be a valid binary search tree.
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.

Note

理解快排。注意，作为pivot的元素在递归时要exclude出来。

Solution

Last as pivot

public class Solution {
    public int median(int[] nums) {
        return helper(nums, 0, nums.length-1, (nums.length-1)/2);
    }
    public int helper(int[] A, int start, int end, int k) {
        int l = start, r = end;
        int pivot = end, a = A[pivot];
        while (l < r) {
            while (l < r && A[l] < a) l++;
            while (l < r && A[r] >= a) r--;
            swap(A, l, r);
        }
        swap(A, l, end);
        if (l == k) return A[l];
        else if (l < k) return helper(A, l+1, end, k);
        else return helper(A, start, l-1, k);
    }
    public void swap(int[] A, int l, int r) {
        int temp = A[l];
        A[l] = A[r];
        A[r] = temp;
    }
}