首页 > 代码库 > 剑指offer (36) 数组中的逆序对

剑指offer (36) 数组中的逆序对

2024-07-09 16:33:17   217人阅读

题目：在数组中的两个数字如果前面一个数字大于后面一个数字，则这两个数字组成一个逆序对

 

题解分析：

首先应该想到很简单的一种解法，顺序遍历数组，对每个数，逐个比较该数字和其以后的数字，T(n) = O(n^2)

 

（1）总体的意思就是将数组分成两段，首先求段内的逆序对数量，比如下面两段代码就是求左右两端数组段内的逆序对数量

count += Merge(data, temp, first, mid);//找左半段的逆序对数目count += Merge(data, temp, mid + 1, end);//找右半段的逆序对数目

 

（2）然后求相邻两个有序段间的逆序对数量

首先两个相邻段都是各自有序的，范围分别是：[first, mid]  [mid + 1, last]

我们设两个游标 i 和 j 分别指示两个有序段的最末位置： i = mid  j = last

注意：我们求两段之间的逆序对的同时需要将这两段最终保持有序

这里需要有一个temp数组，先将结果暂存于temp中，最后将temp复制到data中

暂存temp时，我们从最末位置last开始向前移动

 

我们不断比较data[i] 和 data[j]：

如果data[i] > data[j] ,因为 后一段是有序的，所以data[i]大于后一段中 [mid + 1, j]中的每个值, 此时需要暂存temp，并且增加逆序数

如果data[i] <= data[j], 此时只需要暂存temp即可

 

int Merge(std::vector<int>& data, std::vector<int>& temp, int first, int last){    if (first == last) {        temp.at(first) = data.at(first);        return 0;    }    int mid = first + (last - first) / 2;    int left  = Merge(data, temp, first, mid);    int right = Merge(data, temp, mid + 1, last);    int i = mid;    int j = last;    int tempIndex = last;    int count = 0;    while (i >= first && j >= mid + 1) {        if (data.at(i) > data.at(j)) {            temp.at(tempIndex--) = data.at(i--);            count += (j - (mid + 1) + 1);        } else {            temp.at(tempIndex--) = data.at(j--);        }    }    while (i >= first) {        temp.at(tempIndex--) = data.at(i--);    }    while (j >= mid + 1) {        temp.at(tempIndex--) = data.at(j--);    }
    std::copy(temp.begin() + first, temp.begin() + last + 1, data.begin() + first);    return left + right + count;}int InvertPairs(std::vector<int>& data, std::vector<int>& temp){    if (data.size() == 0) {        return 0;    }    int count = Merge(data, temp, 0, data.size() - 1);    return count;}

 

 

 

 


联系
我们