1. Reverse Pairs——分治算法
   Given an array nums, we call (i, j) an important reverse pair if i < j and nums[i] > 2nums[j].
   You need to return the number of important reverse pairs in the given array.
   Example1:
   Input: [1,3,2,3,1]
   Output: 2
   Example2:
   Input: [2,4,3,5,1]
   Output: 3
   分析：采用類似于歸并算法的思想：不斷的將數(shù)組對半拆分成子數(shù)組，拆到最小的數(shù)組后開始排序，然后一層一層的返回，最后原數(shù)組也是有序的了。
   In each round, we divide our array into two parts and sort them. So after "int cnt = mergeSort(nums, s, mid) + mergeSort(nums, mid+1, e); ", the left part and the right part are sorted and now our only job is to count how many pairs of number (leftPart[i], rightPart[j]) satisfies leftPart[i] <= 2rightPart[j].
   For example,
   left: 4 6 8 right: 1 2 3
   so we use two pointers to travel left and right parts. For each leftPart[i], if j<=e && nums[i]/2.0 > nums[j], we just continue to move j to the end, to increase rightPart[j], until it is valid. Like in our example, left's 4 can match 1 and 2; left's 6 can match 1, 2, 3, and left's 8 can match 1, 2, 3. So in this particular round, there are 8 pairs found, so we increases our total by 8.

 public int reversePairs(int[] nums) {
        return  mergeSort(nums, 0 , nums.length-1);
    }
    
    public int mergeSort(int[] nums, int s, int e){
        if(s>=e)
            return 0;
        int mid = s + (e-s)/2;
        int result = mergeSort(nums, s, mid) + mergeSort(nums, mid+1, e);
        for(int i=s, j=mid+1; i<=mid; i++){
            while(j<=e && nums[i]>2.0*nums[j])
                j++;
            result += j-(mid+1);
        }
        Arrays.sort(nums,s, e+1);
        return result;
    }

2. Kth Largest Element in an Array
   Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
   Example 1:
   Input: [3,2,1,5,6,4] and k = 2
   Output: 5
   分析：借用快排的思想，解決這個問題

class Solution {
    public int findKthLargest(int[] nums, int k) {
        return findKthLargest(nums,0, nums.length-1, nums.length-k);
    }
    
    public int findKthLargest(int[] nums, int start, int end, int k){
        if(start>end)
            return Integer.MAX_VALUE; 
        
        int pivot = nums[end];
        int newIndex = start;
        for(int i =start; i <end; i++){
            if(nums[i]<=pivot){  // Put numbers < pivot to pivot's left
                swap(nums, newIndex, i);
                newIndex++;
            }
        }
        swap(nums, newIndex, end);
        if(newIndex == k)// Found kth smallest number
            return nums[newIndex];
        else if(newIndex < k)// Check right part
            return findKthLargest(nums, newIndex+1, end, k);
        else { // Check left part
            return findKthLargest(nums, 0, newIndex-1, k);
        }
    }
    
    public void swap(int[] nums, int i ,int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

3. K Closest Points to Origin
   We have a list of points on the plane. Find the K closest points to the origin (0, 0).
   (Here, the distance between two points on a plane is the Euclidean distance.)
   You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in.)
   Example 1:
   Input: points = [[1,3],[-2,2]], K = 1
   Output: [[-2,2]]
   Explanation:
   The distance between (1, 3) and the origin is sqrt(10).
   The distance between (-2, 2) and the origin is sqrt(8).
   Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
   We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].
   分析：利用快排思想

class Solution {
    public static int[][] kClosest(int[][] points, int K) {
        int len = points.length;
        return findKClosest(points, 0, len-1, K);
    }

    public static int[][] findKClosest(int[][] points, int start, int end, int K){
        if(start > end)
            return null;

        // quict sort
        int i=start, j=end;
        int[] pivot = points[i];
        while(i < j){
            while(i<j && compare(points[j],pivot)>=0 )
                j--;
            points[i] = points[j];
            while(i<j && compare(points[i],pivot)<=0)
                i++;
            points[j] = points[i];
        }
        points[i] = pivot;

        // judge
        if(i==K-1){
            return Arrays.copyOfRange(points, 0, K);
        }
        else if(i<K-1){
            return findKClosest(points, i+1, end, K);
        }
        else
            return findKClosest(points, start, i-1, K);
    }

    private static int compare(int[] p1, int[] p2) {
        return p1[0] * p1[0] + p1[1] * p1[1] - p2[0] * p2[0] - p2[1] * p2[1];
    }
}