【剑指offer】数组中的逆序对，C++实现

原创博文，转载请注明出处！
本题牛客网地址

1.题目

2.思路

3.代码

  1 class Solution {

  2 public:

  3     int InversePairs(vector<int> data) {

  4         if(data.size() == 0){

  5             return 0;

  6         }

  7         // 排序的辅助数组

  8         vector<int> copy;

  9         for(int i = 0; i < data.size(); ++i){

 10             copy.push_back(data[i]);

 11         }

 12         return InversePairsCore(data, copy, 0, data.size() - 1) % 1000000007;

 13     }

 14     long InversePairsCore(vector<int> &data, vector<int> &copy, int begin, int end){

 15         // 如果指向相同位置，则没有逆序对。

 16         if(begin == end){

 17             copy[begin] = data[end];

 18             return 0;

 19         }

 20         // 求中点

 21         int mid = (end + begin) >> 1;

 22         // 使data左半段有序，并返回左半段逆序对的数目

 23         long leftCount = InversePairsCore(copy, data, begin, mid);

 24         // 使data右半段有序，并返回右半段逆序对的数目

 25         long rightCount = InversePairsCore(copy, data, mid + 1, end);

 26

 27         int i = mid; // i初始化为前半段最后一个数字的下标

 28         int j = end; // j初始化为后半段最后一个数字的下标

 29         int indexcopy = end; // 辅助数组复制的数组的最后一个数字的下标

 30         long count = 0; // 计数，逆序对的个数，注意类型

 31

 32         while(i >= begin && j >= mid + 1){

 33             if(data[i] > data[j]){

 34                 copy[indexcopy--] = data[i--];

 35                 count += j - mid;

 36             }

 37             else{

 38                 copy[indexcopy--] = data[j--];

 39             }

 40         }

 41         for(;i >= begin; --i){

 42             copy[indexcopy--] = data[i];

 43         }

 44         for(;j >= mid + 1; --j){

 45             copy[indexcopy--] = data[j];

 46         }

 47         return leftCount + rightCount + count;

 48     }

 49 };

巴特西

【剑指offer】数组中的逆序对，C++实现

最新文章

热门文章