求逆序对数（分治法）

2024-06-17 08:01| 来源: 网络整理| 查看: 265

核心思路：利用分治将问题折半，认为分成的两个子问题均有解并已返回，因此原问题就转化成如何处理跨越两个子问题部分的逆序对数。

子问题有解：是分治的基本假设，（同数学归纳法假设n=k时成立）即假设该问题是有解的，换种方式理解就是在不断递归的过程中，我们最先处理到的是当序列长度为1的情况，毫无疑问返回0。然后再处理将两个子序列合并的过程，合并后整个序列又可以作为更长序列的子序列。因此只要我们能够处理序列合并，该问题可解。

序列合并：合并时由于我们追求O（nlogn）的时间复杂度，由主定理可知合并操作必须是n的量级，这要求两个子序列需要有序。而递归到序列长度为1时，可认为两个长度为1的序列分别有序，在合并时，按照归并排序合并的方法将二者合并，成为一个有序的序列，作为其他更大的序列的子序列。

而序列合并过程中，在两个子序列有序的基础上，求逆序对数时间复杂度达到O（n）的方法是：

采用两个指针，分别指向两个序列的开头，倘若右边序列当前元素小于左边序列当前元素，则左边序列从当前指向位置到结束均与右边序列指向元素构成逆序对，之后将右边序列当前元素放入临时数组中，右边指针右移；倘若倘若左边序列当前元素小于等于右边序列当前元素，则该元素不可能与右边序列的任何一个元素构成逆序数，只需将该元素放入临时数组中，指针右移即可。

代码：

int NumOfReverseOrderPair(int* A, int begin, int end) { //A为原数组，a为临时数组 //p,q分别指向左，右序列的第一个元素 if (begin == end)return 0; int a[30] = { 0 }, i = 0, p = begin, q = (begin + end) / 2 + 1, num = 0; int num1 = NumOfReverseOrderPair(A, begin, (begin + end) / 2); int num2 = NumOfReverseOrderPair(A, (begin + end) / 2 + 1, end); i = 0; while (p

【本文地址】

公司简介

联系我们