大连建设监察执法网站,备案时网站服务内容,qq引流推广软件免费,广东seo推广软件题目描述在数组中的两个数字#xff0c;如果前面一个数字大于后面的数字#xff0c;则这两个数字组成一个逆序对。输入一个数组#xff0c;求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007输入描述:题目保证输入的数组中没有的相同的…题目描述在数组中的两个数字如果前面一个数字大于后面的数字则这两个数字组成一个逆序对。输入一个数组求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007输入描述:题目保证输入的数组中没有的相同的数字
数据范围
对于%50的数据,size10^4
对于%75的数据,size10^5
对于%100的数据,size2*10^5示例输入
{1, 2, 3, 4, 5, 6, 7, 0}
返回值
7解题思路及代码方法一暴力列举暴力列举所有的数对然后判断是否逆序。具体方法是按住一个arr[i], 依次判断{i1 ... n-1]是否满足条件。n为数组的大小。代码如下class Solution {
private:const int kmod 1000000007;
public:int InversePairs(vectorint data) {int ret 0;int n data.size();for (int i 0; i n; i) {for (int j i 1; j n; j) {if (data[i] data[j]) {ret 1;ret % kmod;}}}return ret;}
};
对于10^5数据O(N^2)算法显然超时。时间复杂度O(N^2)空间复杂度O(1)方法二归并排序思想对数组一边进行归并排序一边计算逆序对。首先明确归并排序的过程递归划分整个区间为基本相等的左右两个区间合并两个有序区间归并排序的代码// 合并过程
void merge__(vectorint arr, int l, int mid, int r) {// 在这个地方创建额外空间是一种不好的做法更好的做法是直接在最外层开辟一个足够大的数组然后传引用到函数。vectorint tmp(r - l 1);int i l, j mid 1, k 0;while (i mid j r) {if (arr[i] arr[j]) {tmp[k] arr[j];}else {tmp[k] arr[i];}}while (i mid) {tmp[k] arr[i];}while (j r) {tmp[k] arr[j];}for (k 0, i l; i r; i, k) {arr[i] tmp[k];}
}// 递归划分过程
void merge_sort__(vectorint arr, int l, int r) {// 只有一个数字则停止划分if (l r) {return;}int mid l ((r - l) 1);merge_sort__(arr, l, mid);merge_sort__(arr, mid 1, r);// 合并两个有序区间merge__(arr, l, mid, r);
}
// 要排序的数组 arr
void merge_sort(vectorint arr) {merge_sort__(arr, 0, arr.size() - 1);
}
本题中如何利用归并排序的思想如果两个区间为[4, 3] 和[1, 2]那么逆序数为(4,1),(4,2),(3,1),(3,2)同样的如果区间变为有序比如[3,4] 和 [1,2]的结果是一样的也就是说区间有序和无序结果是一样的。但是如果区间有序会有什么好处吗当然如果区间有序比如[3,4] 和 [1,2]如果3 1, 显然3后面的所有数都是大于1 这里为 4 1, 明白其中的奥秘了吧。所以我们可以在合并的时候利用这个规则。代码如下class Solution {
private:const int kmod 1000000007;
public:int InversePairs(vectorint data) {int ret 0;// 在最外层开辟数组vectorint tmp(data.size());merge_sort__(data, tmp, 0, data.size() - 1, ret);return ret;}void merge_sort__(vectorint arr, vectorint tmp, int l, int r, int ret) {if (l r) {return;}int mid l ((r - l) 1);merge_sort__(arr, tmp, l, mid, ret);merge_sort__(arr, tmp, mid 1, r, ret);merge__(arr, tmp, l, mid, r, ret);}void merge__(vectorint arr, vectorint tmp, int l, int mid, int r, int ret) {int i l, j mid 1, k 0;while (i mid j r) {if (arr[i] arr[j]) {tmp[k] arr[j];// 奥妙之处ret (mid - i 1);ret % kmod;}else {tmp[k] arr[i];}}while (i mid) {tmp[k] arr[i];}while (j r) {tmp[k] arr[j];}for (k 0, i l; i r; i, k) {arr[i] tmp[k];}}};
Java 版private long cnt 0;
private int[] tmp; // 在这里声明辅助数组而不是在 merge() 递归函数中声明public int InversePairs(int[] nums) {tmp new int[nums.length];mergeSort(nums, 0, nums.length - 1);return (int) (cnt % 1000000007);
}private void mergeSort(int[] nums, int l, int h) {if (h - l 1)return;int m l (h - l) / 2;mergeSort(nums, l, m);mergeSort(nums, m 1, h);merge(nums, l, m, h);
}private void merge(int[] nums, int l, int m, int h) {int i l, j m 1, k l;while (i m || j h) {if (i m)tmp[k] nums[j];else if (j h)tmp[k] nums[i];else if (nums[i] nums[j])tmp[k] nums[i];else {tmp[k] nums[j];this.cnt m - i 1; // nums[i] nums[j]说明 nums[i...mid] 都大于 nums[j]}k;}for (k l; k h; k)nums[k] tmp[k];
}时间复杂度O(NlogN)空间复杂度O(N)解析参考来自数组中的逆序对_牛客网www.nowcoder.com
