【LeetCode】【剑指offer】【数组中的逆序对】

剑指 Offer 51. 数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例 1:

输入: [7,5,6,4]
输出: 5
 

限制：

0 <= 数组长度 <= 50000

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这是我首先想到的写法，就是遍历容器中的每一个元素，查看他后面的元素中有多少个元素比它小。但是这种方法的时间复杂度为O2" role="presentation">O2$O^2$，超出了时间限制

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        int count=0;
        for(int i=0;isize();i++)
        {
            int bigger=nums[i];
            for(int j=i+1;jsize();j++)
            {
                if(nums[j]
                {
                    count++;
                }
            }
        }
        return count;
    }
};

 

下面是对于官方的代码的解读，官方是采用归并排序的思想，在归并的同时进行统计逆序数对的。

与归并相关的代码可以参考归并排序+计数排序【C语言数据结构】_桜キャンドル淵的博客-CSDN博客

1

3

5

7

2

4

6

8

 

 这里我们对比left和right的位置的数据，left的位置比较小，所以我们将left位置的数据拷贝到我们的tmp中

1

3

5

7

2

4

6

8

tmp

1

 

这里我们right指向的数据更小，所以我们将right的数据拷贝到我们的tmp中 ，然后right++

1

3

5

7

2

4

6

8

tmp

1

2

 

这里我们的left小于right，同时也说明right到mid之间的数据都是小于left当前指向的数据的，所以我们需要给我们最终的逆序数的统计个数加上right-(mid+1)，其中right=5，mid=(0+7)/2=3，也就是5-(3+1)=1也就是有一个逆序对，也就是3在2前面这一组逆序对

1

3

5

7

2

4

6

8

tmp

1

2

3

这里我们的right指向的数据比left小，我们将right中的数据拷贝到tmp中 

1

3

5

7

2

4

6

8

tmp

1

2

3

4

 

这时我们的left的数据小于了right位置的数据，也就是说right前到mid之间的数据全部都是小于5，也就是2,4，和5组成了两组逆序数对，所以给我们的结果加上right-(mid+1)也就是6-(3+1)=2；

1

3

5

7

2

4

6

8

tmp

1

2

3

4

5

这时我们的right指向的数据更小，所以将right中的数据拷贝到tmp数组中，right++

1

3

5

7

2

4

6

8

tmp

1

2

3

4

5

6

 

这里我们 right中的数据大于left中的数据，也就是说我们right前到mid之间的数据都是比当前left所指向的数据更小的，所以我们给我们的逆序数结果集加上right-(mid+1)也就是7-(3+1)=3，也就是2,4,6跟7组成了三队逆序数

1

3

5

7

2

4

6

8

tmp

1

2

3

4

5

6

7

 将7拷贝到我们的tmp中之后还剩下一个8，直接将8放到我们的tmp数据末尾我们的逆序数统计和归并数组的排序就完成了。

1

3

5

7

2

4

6

8

tmp

1

2

3

4

5

6

7

8

class Solution {
public:
    int mergeSort(vector<int>& nums, vector<int>& tmp, int l, int r) {
        //如果我们的左边界已经大于了右边界，那么救代表这里并没有逆序对，所以返回0
        if (l >= r) {
            return 0;
        }
 
        //这里我们所采用的是分而治之的思想，获取到当前容器的中间位置，也就是mid
        int mid = (l + r) / 2;
        //递归调用我们的代码，分别将左边区域的和右边区域的逆序对的数据加起来
        int inv_count = mergeSort(nums, tmp, l, mid) + mergeSort(nums, tmp, mid + 1, r);
        //上面那一行代码已经将我们的数据全部都分完组了，下面我们就要对我们已经分完组的数据进行归并
        //这里的l是我们的左边数据左边界，j为我们第二段数据的左边界
        //pos为我们的指针
        int i = l, j = mid + 1, pos = l;
        //这里我们的左半部分为划分成了从l到mid，我们的右半部分被划分成了mid+1到r
        while (i <= mid && j <= r) {
            //这里的i,j分别是我们左半部分的指针和右半部分的指针
            if (nums[i] <= nums[j]) {
                //哪一部分的数据更小，就将哪一部分的数据放到我们的tmp数组中
                //也就是我们排序完后有序的数组
                tmp[pos] = nums[i];
                //这种情况下是我们的nums[i]更小，也就是当前num[i]被放到我们的临时数组中了
                //所以我们需要将i++比较下一个位置
                ++i;
                //这里我们的判断条件时nums[i]<=nums[j]，也就是说当前位置的j才等于i
                //也就是说mid+1到j之前的数据都是小于i位置的数据的
                //也就是说有j-(mid+1)个逆序对
                inv_count += (j - (mid + 1));
            }
            else {
                //这里的分类就是nums[i]>nums[j]也就是说我们的j位置的数据更小
                //所以我们需要将j位置的数据拷贝到我们的pos位置，并且将我们的j指针后移，
                //对后半段下一个位置的数据进行比较
                tmp[pos] = nums[j];
                ++j;
            }
            //当前我们的pos位置已经存过了比较过的数据了，我们在进行下一轮的比较之前
            //需要将pos指针移动到下一个存放比较过的数据的位置
            ++pos;
        }
        //经过上面的比较，在左区间和右区间中一定有一个已经全部拷贝到我们的临时数组中了
        //所以如果我们的左区间还没有拷贝完成的话，也就代表着左区间剩下的元素已经比右区间全部的元素都要大了
        //所以我们需要将剩余的左区间元素拼接到我们的tmp中
        for (int k = i; k <= mid; ++k) {
            tmp[pos++] = nums[k];
            inv_count += (j - (mid + 1));
        }
        //如果左区间已经全部拷贝完了，那么右区间一定还有剩余的元素没有拷贝，
        //右区间中剩余的元素一定比左区间全部的元素更大，所以我们需要将右区间中的剩余元素拷贝到我们的tmp数组中
        for (int k = j; k <= r; ++k) {
            tmp[pos++] = nums[k];
        }
        //将我们排序完成的数据拷贝到我们的原数组中
        //下面就是将我们刚刚排好序的数据，也就是我们的临时数组中的数据
        //tmp.begin()+l到tmp.begin()+r+1拷贝到从我们nums.begin()+l开始的位置
        copy(tmp.begin() + l, tmp.begin() + r + 1, nums.begin() + l);
        //将逆序数对的个数的结果返回
        return inv_count;
    }
 
    int reversePairs(vector<int>& nums) {
        int n = nums.size();
        vector<int> tmp(n);
        return mergeSort(nums, tmp, 0, n - 1);
    }
};