2019-08-22 分治算法

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
   分析：采用类似于归并算法的思想：不断的将数组对半拆分成子数组，拆到最小的数组后开始排序，然后一层一层的返回，最后原数组也是有序的了。
   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];
    }
}