lintcode 532 Reverse Pairs（mergesort）（求逆序对对数）（二分插入排序）

链接：https://www.lintcode.com/problem/reverse-pairs/description

求逆序对对数，盲猜暴力超时

手写mergesort；

比如左右都是排好序的； 2 4 ，1 3 由于2>1,mid=2,对数就是（mid-i+1)对，(2,1),(4,1);

类似于一个mergesort板子；

code:

 1 class Solution {
 2 public:
 3     /**
 4      * @param A: an array
 5      * @return: total of reverse pairs
 6      */
 7     long long reversePairs(vector<int> &nums) {
 8         // write your code here
 9         return mergesort(nums,0,nums.size()-1);
10     }
11     int mergesort(vector<int> &nums,int left,int right){
12         if(left>=right) return 0;
13         int mid=left+(right-left)/2;
14         //result of left and right; sort left ans right
15         int result=mergesort(nums,left,mid)+mergesort(nums,mid+1,right);
16         result += merge(nums,left,right,mid);
17         return result;
18     }
19     int merge(vector<int>& nums,int left,int right,int mid){
20         //calculate pairs
21         int result=0;
22         int merged[100010] ;
23         int i=left,j=mid+1,index=0;
24         while(i<=mid && j<=right){
25             if(nums[i]<=nums[j])
26               merged[index++]=nums[i++];
27              else{
28                  merged[index++]=nums[j++];
29                  result+=mid-i+1;
30              }
31         }
32         while(i<=mid){
33             merged[index++]=nums[i++];
34         }
35         while(j<=right){
36             merged[index++]=nums[j++];
37         }
38         for(i=left,index=0; i<=right; i++,index++){
39             nums[i]=merged[index];
40         }
41         return result;
42     }
43 };

另：二分搜索（二分插入排序），思路是将给定数组从最后一个开始，用二分法插入到一个新的数组，这样新数组就是有序的，那么此时该数字在新数组中的坐标就是原数组中其右边所有较小数字的个数，（插入排序）

每次倒序插入最右时，说明前边的几个数都比它小，即逆序数的对数(下标从0开始，所以不需要额外减一；

// 5 
// 2 9 6 7 4
// 5
第一次：有序：4                     无序： 7 6 9 2   r=0；
第二次：有序：4 7                  无序： 6 9 2      r=1；（插入第2个位置，下标为1）
都三次：有序：4 6 7               无序： 9 2         r=1；（插入第2个位置，下标为1）
第四次：有序：4 6 7 9            无序： 2            r=3；（插入第4个位置，下标为3）
第五次：有序：2 4 6 7 9         无序：               r=0；
简言之，在从后往前插入的过程中找当前位置前边有几个数，（比它小的）
如果从前往后找的话，比它大的数是未知状态，不好计算；

 1 class Solution {
 2 public:
 3     long long reversePairs(vector<int>& A) {
 4         long long res = 0;
 5         vector<int> v;
 6         for (int i = A.size() - 1; i >= 0; --i) {
 7             int left = 0, right = v.size();
 8             while (left < right) {
 9                 int mid = left + (right - left) / 2;
10                 if (A[i] > v[mid]) left = mid + 1;
11                 else right = mid;
12             }
13             v.insert(v.begin() + right, A[i]);
14             res += right;
15         }
16         return res;        
17    }
18 };