数组中的逆序对
·
LuYanFCP
面试题51. 数组中的逆序对 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4]
输出: 5
限制： 0 <= 数组长度 <= 50000
解决思路
暴力解法
直接进行无脑扫描
1class Solution {
2public:
3 int reversePairs(vector<int>& nums) {
4 if (nums.size() == 0)
5 return 0;
6 int sum = 0;
7 for (int i = 0; i < nums.size() - 1; ++i) {
8 for (int j = i+1; j < nums.size(); ++j) {
9 if (nums[i] > nums[j])
10 sum++;
11 }
12 }
13 return sum;
14 }
15};
时间复杂度$O(n^2)$，空间复杂度$O(1)$
超时！，考虑新的算法。
分治法
这个题目有很好的分治法的特征
- 左右相互独立，可以拆分为两个任务
- 基本思路是： 计算左半部分的逆序个数+计算右半部分+跨边界的逆序数
定义函数_reversePairs用来实现分治法，则solution函数为
1int _reversePairs(vector<int>& nums, int begin, int end);
2
3int reversePairs(vector<int>& nums) {
4 return _reversePairs(nums, 0, nums.size());
5}
现在看_reversePairs函数内部
思路：计算左半部分的逆序个数+计算右半部分+跨边界的逆序数， 使用递归的方式求解
- 递归的结束条件: begin >= end 为结束条件
- 找到中间值，递归计算左边的逆序数，递归计算右边的逆序数
- 跨边界的逆序数计算
- 加和并返回
算法核心是处理 跨边界的逆序数的计算
观察到左右都是无序的，如果是有序的话可以提高计算跨边界的逆序数计算的速度。
因此联想到了归并排序，因为归并排序就是左右有序的。考虑使用归并排序来解决这个问题。
具体思想为：在merge过程中，需要对比左右两个序列的值
1#include <vector>
2#include <iterator>
3#include <iostream>
4using std::vector;
5
6class Solution {
7public:
8 int reversePairs(vector<int>& nums) {
9 temp = new int[nums.size()];
10 return _reversePairs(nums, 0, nums.size()-1);
11 }
12
13 int _reversePairs(vector<int>& nums, int begin, int end) {
14
15 if (begin < end) {
16 int mid = (end - begin)/2 + begin;
17 int left_rp = _reversePairs(nums, begin, mid); // 已排好
18 int right_rp = _reversePairs(nums, mid+1, end);
19 // 两边执行完毕之后就已经是排好序了
20 int i = begin, j = mid+1, k = begin;
21 int grap_rp = 0;
22 while (i <= mid && j <= end) {
23 if (nums[i] <= nums[j]) {
24 temp[k++] = nums[i++];
25 grap_rp += j - mid - 1;
26 } else {
27 // nums[i] > nums[j]
28 temp[k++] = nums[j++];
29 }
30 }
31
32 // 1 3 5 7 9 <= mid
33 // 4 5 6 8 10
34 //
35 while (i <= mid) {
36 temp[k++] = nums[i++];
37 grap_rp += j - mid - 1;
38 }
39 while (j <= end) temp[k++] = nums[j++];
40 std::copy(temp+begin, temp+end+1, nums.begin()+begin);
41 // std::copy(temp+begin, temp+end+1, std::ostream_iterator<int>(std::cout, " "));
42 // std::cout << std::endl;
43 // std::cout << "left_rp: " << left_rp << " right_rp: " << right_rp << " grap_rp: " << grap_rp << endl;
44 return left_rp + right_rp + grap_rp;
45 } else {
46 return 0;
47 }
48
49 }
50private:
51 int *temp;
52};
执行完毕：得到结果为：
执行用时 :
- 148 ms, 在所有 C++ 提交中击败了92.74%的用户
- 内存消耗 :47.1 MB, 在所有 C++ 提交中击败了100.00%的用户
使用hash去求解
构建一个hashtable去记录数字x出现的次数，因此如果求逆序的话就是计算当前数字v到末尾n的hashtable的值的sum，这样遍历一般数列，因此其时间复杂度为$O(n\*K)$，其中K为最大值(因为如果hashtable要容纳所有值的话必须有所有值的索引)。如果K很大的话其计算的复杂度是不可接受的。 因此我们引入离散化，就是将nums中的数字从小到大排序，去除重复的然后使用hashmap去索引每一个数字，将其的索引为1~n，这样的话时间复杂度会降到 $O(n\*2)$ 与暴力方法相同，也不可接受。
因此为了简化hashtable的值的sum的计算，我们引入树状数组去解决此问题，可以将时间复杂度降低到$O(nlogn)$
树状数组(BIT)
这个方法的核心是 树状数组 + 离散化
离散化
离散化用于处理，使用树状数组可能引发， 数组hash过长的问题
1vector<int> vec_elem;
2std::copy(nums.begin(), nums.end(), std::back_insert_iterator(vec_elem));
3sort(vec_elem.begin(), vec_elem.end());
4// 删除重复的
5vec_elem.erase(unique(vec_elem.begin(), vec_elem.end), vec_elem.end());
6// 离散化操作
7int count = 1; // 标记计数
8unordered_map<int, int> hashmap;
9for (int elem : vec_elem) {
10 hashmap[elem] = count++;
11}
将一些列递增的数列转换位1-n的标号
离散化的操作只适合离线计算不适合在线计算。
树状数组
具体讲解可见我的树状数组总结。 树状数组
构造树状数组去计算，x之前的数比x位置的数大数的个数。其中树状数组记录的标号位x数字的个数。
1vector<int> t(n + 1);
2int ans = 0;
3for (int i = 0; i < nums.size(); ++i) {
4 add(hashmap[nums[i]], t);
5 ans += (i+1) - ask(hashmap[nums[i]], t); // 正序数+逆序数=i+1
6}
7return ans;
所有的代码
- 执行用时 :208 ms, 在所有 C++ 提交中击败了66.29%的用户
- 内存消耗 :61.1 MB, 在所有 C++ 提交中击败了100.00%的用户
1#include <vector>
2#include <algorithm>
3#include <unordered_map>
4#include <iterator>
5
6using std::vector;
7using std::sort;
8using std::unique;
9using std::unordered_map;
10
11class Solution {
12public:
13 int lowbit(int x) {
14 return x & (-x);
15 }
16 void add(int x, vector<int>& t) {
17 int n = t.size() - 1;
18 for (; x <= n; x += lowbit(x)) t[x] += 1;
19 }
20 int ask(int x, vector<int>& t) {
21 int res = 0;
22 for (; x > 0; x -= lowbit(x)) res += t[x];
23 return res;
24 }
25 int reversePairs(vector<int>& nums) {
26 int n = nums.size();
27 // 离散化操作
28 vector<int> vec_elem;
29 std::copy(nums.begin(), nums.end(), std::back_insert_iterator(vec_elem));
30 sort(vec_elem.begin(), vec_elem.end()); // 删除重复的
31 vec_elem.erase(unique(vec_elem.begin(), vec_elem.end()), vec_elem.end());
32 int count = 1; // 标记计数
33 unordered_map<int, int> hashmap;
34 for (int elem : vec_elem) {
35 hashmap[elem] = count++;
36 }
37 vector<int> t(n + 1);
38 int ans = 0;
39 for (int i = 0; i < nums.size(); ++i) {
40 add(hashmap[nums[i]], t);
41 ans += (i+1) - ask(hashmap[nums[i]], t);
42 }
43 return ans;
44 }
45};