1 数组中的逆序对

问题描述

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

问题分析

策略选择

  • 数据结构：线性数组
  • 算法思想：变治法。将搜索查找问题修改为排序问题。归并排序

算法设计

  • 归并排序」是分治思想的典型应用，它包含这样三个步骤：

    • 分解： 待排序的区间为 [l, r]，令 $m = \lfloor \frac{l + r}{2} \rfloor$，我们把 [l, r] 分成 [l,m] 和 [m+1,r]
    • 解决： 使用归并排序递归地排序两个子序列
    • 合并： 把两个已经排好序的子序列 [l, m][l,m] 和 [m + 1, r][m+1,r] 合并起来

  • 在归并排序过程中。后边列表的数添加到前边之后。前边列表中数的量，就是本次排序逆序数的量。

算法分析

  • 时间复杂度：同归并排序 O(nlogn)。
  • 空间复杂度：同归并排序 O(n)，

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
class Solution {
public:
    int reversePairs(vector<int>& nums) {

        int count=0;
        vector<int> temps(nums.size());
        merge_sort(nums,0,nums.size()-1,count,temps);
        return count;

    }
    int merge_sort(vector<int>&nums,int beg,int end,int &count,vector<int>&temps){
        //进行头递归,分解
        int mid=0;
        if(beg<end){
            mid=(beg+end)/2;
            merge_sort(nums,beg,mid,count,temps);
            merge_sort(nums,mid+1,end,count,temps);
        }
        else{
            return 0;
        }

        //进行合并
        int k=beg,i=beg,j=mid+1;
        while(k<=end){
            if(i==mid+1){
                temps[k++]=nums[j++];
                continue;
            }
            if(j==end+1){
                temps[k++]=nums[i++];
                continue;
            }
            if(nums[i]<=nums[j]){
                temps[k++]=nums[i++];
            }
            else{
                temps[k++]=nums[j++];
                count+=mid-i+1;
            }
        }
        for(int m=beg;m<=end;m++){
            nums[m]=temps[m];
        }
        return 0;

    }
};