问题描述
- 问题链接：AcWing 788. 逆序对的数量
解法一
分析
-
考点：归并排序。
-
归并排序是分治的思想，即将原问题转化为更小的子问题。
-
我们将序列从中间分开，将逆序对分成三类：（1）两个元素都在左边；（2）两个元素都在右边；（3）两个元素一个在左一个在右；
-
计算步骤是：（1）递归算左边的；（2）递归算右边的；（3）算一个左一个右的；（4）把他们加到到一起。
-
这个时候我们注意到一个很重要的性质，左右半边的元素在各自任意调换顺序，是不影响第三步计数的，因此我们可以数完就给它排序。
-
当对两个已经排好序的子区间nums[l, mid]、nums[mid+1, r]进行归并时，如果nums[i] > nums[j]，l<=i<=mid, mid+1<=j<=r时，第（3）类逆序对的数量为mid-i+1个。
-
时间复杂度： O ( n × l o g ( n ) ) O(n times log(n)) O(n×log(n))，n为数组长度。
代码
- C++
#includeusing namespace std; typedef long long LL; const int N = 100010; int n; int q[N], tmp[N]; LL merge_sort(int l, int r) { if (l >= r) return 0; int mid = l + r >> 1; LL res = merge_sort(l, mid) + merge_sort(mid + 1, r); int i = l, j = mid + 1, k = 0; while (i <= mid && j <= r) if (q[i] <= q[j]) tmp[k++] = q[i++]; else { res += mid - i + 1; tmp[k++] = q[j++]; } while (i <= mid) tmp[k++] = q[i++]; while (j <= r) tmp[k++] = q[j++]; for (int i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j]; return res; } int main() { cin >> n; for (int i = 0; i < n; i++) cin >> q[i]; cout << merge_sort(0, n - 1) << endl; return 0; }
解法二
分析
-
考点：树状数组、离散化。考点详解网址：树状数组、离散化。
-
因为数据在 1 0 9 10^9 109 量级，作为树状数组的下标太大了，空间不够用，因此需要进行离散化，因为需要比较数值的大小，因此需要保序离散化。
-
从左到右遍历数组中的每个元素，使用树状数组统计当前遍历元素的前面元素出现次数。对于当前遍历的元素q[i]，找到其离散化后的值t，答案加上大于t的数的个数即可。
-
时间复杂度： O ( n × l o g ( n ) ) O(n times log(n)) O(n×log(n))，n为数组长度。
代码
#include2. 扩展例题 剑指 Offer 51 数组中的逆序对#include #include #include using namespace std; typedef long long LL; const int N = 100010; int n; int q[N]; int tr[N]; // 树状数组 vector alls; // 用于离散化 int lowbit(int x) { return x & -x; } void add(int x, int v) { for (int i = x; i <= N; i += lowbit(i)) tr[i] += v; } int query(int x) { int res = 0; for (int i = x; i; i -= lowbit(i)) res += tr[i]; return res; } int find(int x) { return lower_bound(alls.begin(), alls.end(), x) - alls.begin() + 1; } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &q[i]); alls.push_back(q[i]); } sort(alls.begin(), alls.end()); alls.erase(unique(alls.begin(), alls.end()), alls.end()); LL res = 0; for (int i = 0; i < n; i++) { int t = find(q[i]); // 获取q[i]离散化后的值 res += query(N - 1) - query(t); add(t, 1); } printf("%lldn", res); return 0; }
问题描述
- 问题链接：剑指 Offer 51 数组中的逆序对
分析
- 这里使用归并方式的求解。
代码
- C++
class Solution {
public:
vector tmp;
int reversePairs(vector& nums) {
int n = nums.size();
tmp.resize(n);
return merge_sort(nums, 0, nums.size() - 1);
}
int merge_sort(vector &nums, int l, int r) {
if (l >= r) return 0;
int mid = l + r >> 1;
int res = merge_sort(nums, l, mid) + merge_sort(nums, mid + 1, r);
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r)
if (nums[i] <= nums[j]) tmp[k++] = nums[i++];
else {
tmp[k++] = nums[j++];
res += mid - i + 1;
}
while (i <= mid) tmp[k++] = nums[i++];
while (j <= r) tmp[k++] = nums[j++];
for (int i = l, j = 0; i <= r; i++, j++) nums[i] = tmp[j];
return res;
}
};
时空复杂度分析
-
时间复杂度： O ( n × l o g ( n ) ) O(n times log(n)) O(n×log(n))，n为数组长度。
-
空间复杂度： O ( n ) O(n) O(n)。
题目描述：Leetcode 0493 翻转对
分析
- 因为要统计nums[i] > 2*nums[j]数对的数量，因此统计数量和归并排序需要分开进行。
代码
- C++
class Solution {
public:
vector tmp;
int reversePairs(vector& nums) {
tmp = vector(nums.size());
return merge_sort(nums, 0, nums.size() - 1);
}
int merge_sort(vector &nums, int l, int r) {
if (l >= r) return 0;
int mid = l + r >> 1;
int res = merge_sort(nums, l, mid) + merge_sort(nums, mid + 1, r);
{
int i = l, j = mid + 1;
while (i <= mid && j <= r)
if (nums[i] > nums[j] * 2ll) res += mid - i + 1, j++;
else i++;
}
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r)
if (nums[i] < nums[j]) tmp[k++] = nums[i++];
else tmp[k++] = nums[j++];
while (i <= mid) tmp[k++] = nums[i++];
while (j <= r) tmp[k++] = nums[j++];
for (int i = l, j = 0; i <= r; i++, j++) nums[i] = tmp[j];
return res;
}
};
时空复杂度分析
-
时间复杂度： O ( n × l o g ( n ) ) O(n times log(n)) O(n×log(n))，n为数组长度。
-
空间复杂度： O ( n ) O(n) O(n)。
