数组中的逆序对

数组中的逆序对_牛客题霸_牛客网 (nowcoder.com)

题意

思路

尝试：每次看到这个题，我都老是想记录原来位置然后再排个序看看和原来的差值，即是答案。后面想想快速排序试试，移到前面的+上差值，移到后面的减去差值，中间过程不一定就是差值。

​ 使用归并排序，排序过程中，逆序对会随着元素慢慢移到正确的位置而减少，而且每次减少的逆序对是可以统计的。将两个有序数组进行合并的时候，当右数组的元素移动到左数组的原来位置的时候，减少的逆序对数为移动距离，记录该值即可。

​ 至于取余的问题每次都进行cnt=(cnt+mod)%mod就可以了。

public long cnt = 0;
   public long mod = 1000000007;

   public void Merge(int[] array, int[] temp, int l, int r) {
       if(l>=r)
           return;
       int mid=(l+r)/2;
       int pos=l,lpos=l,rpos=mid+1;
       while (lpos<=mid&&rpos<=r) {
          if (array[lpos]<=array[rpos]){
              temp[pos]=array[lpos];
              lpos++;
          }else {
              temp[pos]=array[rpos];
              cnt+=rpos-pos;
              cnt=(cnt+mod)%mod;
              rpos++;
          }
          pos++;
       }
       while(lpos<=mid){
           temp[pos]=array[lpos];
           lpos++;
           pos++;
       }
       while(rpos<=r){
           temp[pos]=array[rpos];
           rpos++;
           pos++;
       }
       for (int i = l; i <= r; i++) {
           array[i]=temp[i];
       }
   }

   public void MergeSort(int[] array, int[] temp, int l, int r) {
       int cnt;
       if (l >= r)
           return;
       int mid = (l + r) / 2;
       MergeSort(array, temp, l, mid);
       MergeSort(array, temp, mid + 1, r);
       Merge(array,temp, l, r);
   }

   public int InversePairs(int[] array) {
       cnt = 0;
       int[] temp = new int[array.length];
       MergeSort(array, temp, 0, array.length - 1);
       return (int) cnt;
   }

算法全部代码参考leonyan18/AlgorithmCodeInJava (github.com)