题解 | #数组中的逆序对#

利用分治思想对比递归和非递归两种思路。

• 注释为递归算法

• 计数得用unsigned int类型存储，否则会溢出，无法通过最后一个案例。

• 利用do while语句实现非递归
  具体思路为按步从2，4，8，每次翻倍直接进行分治。
  在一步中利用辅助空间vector vec进行排序。

  class Solution {
  public:
    /*
    int mergeSort(int left, int right, vector& data, vector& temp) {
        if (left >= right) return 0;
        int mid = left + ((right - left) >> 1);
        unsigned int ans = mergeSort(left, mid, data, temp) +
                  mergeSort(mid + 1, right, data, temp);
  
        int i = left, j = mid + 1;
        for (int k = left; k <= right; k++)
            temp[k] = data[k];
        for (int k = left; k <= right; k++) {
            if (i > mid)
                data[k] = temp[j++];
            else if (j > right or temp[i]<=temp[j])
                data[k] = temp[i++];
            else {
                data[k] = temp[j++];
                ans += mid - i + 1;
            }
        }
        return ans % 1000000007;
    }
    */
  
    int InversePairs(vector data) {
        unsigned int count = 0;
        int n = data.size();
        int step = 2;
        do {
            for (int i = 0; i < n; i += step) {
                int ii = 0, jj = (step>>1);
                int end = min(i + step,n);
                int mid = jj;
                vector vec(data.begin()+i,data.begin()+end);
                if (jj>=vec.size()) continue;
                for(int k=i;k<end;k++){
                    if (ii==mid) data[k]==vec[jj++];
                    else if(vec[ii]<=vec[jj] or jj==(end-i)){
                        data[k]=vec[ii++];
                    } else {
                        data[k]=vec[jj++];
                        count += mid - ii;
                    }
                }
            }
            step <<= 1;
        } while (step < 2*n);
        return  count % (1000000007);
        /*
        vector res(data.size());
        return mergeSort(0, data.size() - 1, data, res);
        */
    }
  

};
```