逆序对

xiaoxiao2021-02-28  4

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

简单思路是,挨个遍历数组中的元素,每遍历到一个元素之后和后面的元素再逐一比较,这样的复杂度是O(n^2)。 这里时间都花费在了逐一比较上,这样一个个找逆序对显然是比较耗时的。归并排序的思路就是一次性的找出一串来,所以复杂度会低很多,本质就是归并排序的复杂度O(nlogn)。 首先写一个归并排序,只需要做一丁点修改就可以找出逆序对。归并排序假设左右两个子数组都是有序的,然后再merge成一个大的数组,在merge的过程中,如果前面子数组中某一元素的比后面子数组的某个元素大,那么他肯定后面子数组这个元素之前的所有数都要大,也就是都形成了逆序对,这样一来,一次性就找出了一串逆序对,而不是一个个的找。 另外注意,我们一边找逆序对,一边还要排序,这样做是为了防止重复找已经找到的逆序对。

int merge(vector<int> &data, int start, int mid, int end) { vector<int> tmp; int i = start; int j = mid+1; // 右半部子数组开头是mid+1,因为下面右半部子数组不包含mid int cnt = 0; while(i <= mid && j <= end) { if(data[i] <= data[j]) { tmp.push_back(data[i]); i++; } else { cnt += j-mid; // 逆序对,从j开始一直到第二个子数组的头部,都够成了逆序对 tmp.push_back(data[j]); j++; } } // 剩余的子数组merge到tmp while(i <= mid) { tmp.push_back(data[i]); i++; } while (j <= end) { tmp.push_back(data[j]); j++; } for(i=0; i<tmp.size(); i++) // 还需要将排序好的数组复制回原数组 data[start+i] = tmp[i]; return cnt; } int mergeSort(vector<int> &data, int start, int end) { int cnt = 0; if(start < end) { int mid = (start + end)/2; cnt += mergeSort(data, start, mid); //左半部分 包含mid cnt += mergeSort(data, mid+1, end); //右半部分 不包含mid cnt += merge(data, start, mid, end); //合并两部分,并计算数量 } return cnt; } int InversePairs(vector<int> &data) { return mergeSort(data, 0, data.size()-1); }
转载请注明原文地址: https://www.6miu.com/read-1650299.html

最新回复(0)