80.Median

public class Solution {
/**
 * @param nums: A list of integers.
 * @return: An integer denotes the middle number of the array.
 */
private int findK(int[] nums, int start, int end, int k) {
    int target = nums[start];
    int tmpStart = start;
    int tmpEnd = end;
    while (start <= end) {
        while (start <= end && nums[start] <= target) {
            start++;
        }
        while (start <= end && nums[end] > target) {
            end--;
        }
        if (start <= end) {
           swap(nums, start, end);
           start++;
           end--;
        }
    }
    swap(nums, tmpStart, end);
    if (end == k) {
       return nums[end]; 
    } else if (end > k) {
        return findK(nums, tmpStart, end - 1, k);
    } else {
        return findK(nums, end + 1, tmpEnd, k);
    }
}
private void swap(int[] nums, int start, int end) {
    if (nums[start] != nums[end]) {
    nums[start] = nums[start] ^ nums[end];
    nums[end] = nums[start] ^ nums[end];
    nums[start] = nums[start] ^ nums[end];
    }
}
public int median(int[] nums) {
    // write your code here
    return findK(nums, 0, nums.length - 1, (nums.length + 1) / 2 - 1);
}
}