leetCode:数组中的逆序对
文章目录
题目描述
难度困难857收藏分享切换为英文接收动态反馈
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4]
输出: 5
限制：
0 <= 数组长度 <= 50000
解题思路
使用暴力能够解决，就是遇到一个数，就向后面遍历比它小的数就计数。。。遍历完所有数就可以了。
测试了，不出所料，超时。。。。。。。
然后使用树状数组。。。。。。
先不使用树状数组时，另一种解题思路。
使用相对顺序给7,5,6,4编号就变成4,2,3,1
我们使用一个数组tree来记录1,2,3,4每个数的个数，每出现一个数在对应下标++。由于我们需要记录的是逆序，所以我们从后面往前遍历。
当遇到1时，此时tree数组为[0,0,0,0,0]，数下下标1前面的数的总和，总和为0，再把1对应的下标++,此时tree数组为[0,1,0,0,0]。
当遇到3时，此时tree数组为[0,1,0,0,0]，数下下标3前面的数的总和，总和为1,再把3对应的下标++,此时tree数组为[0,1,0,1,0]。
当遇到2时，此时tree数组为[0,1,0,1,0]，数下下标2前面的数的总和，总和为1,再把2对应的下标++,此时tree数组为[0,1,1,1,0]。
当遇到4时，此时tree数组为[0,1,1,1,0]，数下下标4前面的数的总和，总和为3,再把4对应的下标++,此时tree数组为[0,1,1,1,1]。
把上面的总和加起来，就是0+1+1+3 = 5总共有5个逆序对。
但是现在的时间复杂度还是n ^2。。。。。。。。现在可以使用树状数组了，它是专门用来计算区间值和的一个工具，可以把区间求和的时间复杂度由n降低到log^n。。。。。。。。
具体方法就是它会把把数存放到父节点里，然后通过一个函数可以很简单的定位到任何一个数的父节点。。。。
举个例子，比如下标4是下标1,2，3的父节点，那么每加入一个1就在其本身的数外，再在4上面++，加入2也是一样，然后再假设2是1的父节点。那么上述的tree的变迁就是
当没加入时。
当加入1时，此时tree数组为[0,1,1,0,1]，
查询，比3小的数，也就是1-2的和了，通过那个函数得到父节点是2，查询得到结果1,当加入3时，此时tree数组为[0,1,1,1,2]，
查询，比2小的数，也就是1-1的和了，通过那个函数得到父节点是1，查询得到结果1,当加入2时，此时tree数组为[0,1,2,1,3]，
查询，比4小的数，也就是1-3的和了，通过那个函数得到父节点是2和3，查询得到结果2+1 = 3,当加入4时，此时tree数组为[0,1,2,1,4]，
统筹得到结果是1+1+3 = 5.。。。。。这个方法和上面那个方法基本一样，除了多了一个计算父节点的函数。
这个函数解决了当加入数的时候，在那个数的父节点也++，比如加入1时在2,4上面也++
当查询的时候找到查询数的父节点比如查询1-2的时候就能定位到2，查询1-3的时候就能定位到2和3。
。。。。。。。。。。
用到了位运算。。。。。。。
以3为例子，当它加入的时候，它的二进制为0011，给它最低的位补上1就变成了0100也就是4所以它的一个父节点为4，如果再在0100的最低的1补上1，就变成1000，变成了8所以8是4和3的父节点。
当查询1-3的时候，先是它本身，然后它的二进制为0011，给它最低的1去掉，变为0010也就是2，当然还可以继续去掉最低的1，就变成0了`，超出范围，计算停止。
。。。。。
在计算机里面怎么实现的呢？就是使用x & -x，就得到了最低位的数，比如3的二进制为11，那么-3的二进制为11111111111111111111111111111101，用0减去11就知道了，如果细究的话可以去了解一下计算机里面负数的存储也就是补码的相关知识。
。。。。。
那么11 & 11111111111111111111111111111101就是1嘛。
然后计算父节点就是3+1，就变成0100了嘛，再继续计算0100的父节点，就是4 & -4就是0100 & 11111111111111111111111111111100 = 4，那就是4+4 = 8了嘛。。。。
。。。。。。再看查询的时候。。。。。。
11 & 11111111111111111111111111111101 = 1,然后3-1 = 2嘛，然后再继续10 & 11111111111111111111111111111110 = 2，然后2 -2 = 0，超界了，不考虑。
。。。。。。。。。。。。。
具体流程就是这样。
从后往前遍历
遇到一个数，先通过函数查询比它小的数的父节点得到结果，再通过函数计算比它大的父节点，在它的自身以及父节点上面++，方便下次查询。
代码实现
#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
class BIT {
private:
vector<int> tree; //存储各个父节点的值
int n;
public:
BIT(int _n) : n(_n), tree(_n + 1) {} //初始化，全部为0
static int lowbit(int x) { return x & (-x); } //计算最低位的1
int query(int x) { //查询，加上最低位1的位置减去1
int ret = 0;
while (x) {
ret += tree[x];
x -= lowbit(x);
}
return ret;
}
void update(int x) { //加入数时，在最低位1的位置加1
while (x <= n) {
++tree[x];
x += lowbit(x);
}
}
};
class Solution {
public:
int reversePairs(vector<int>& nums) {
int n = nums.size();
vector<int> tmp = nums;
sort(tmp.begin(), tmp.end()); //排序
for (int i = 0; i < nums.size(); i++) {
nums[i] = lower_bound(tmp.begin(), tmp.end(), nums[i]) - tmp.begin() +
1; //计算每个数的相对位置，比如7排在4,5,6,7的第4个
}
BIT bit(n);
int ans = 0;
for (int i = n - 1; i >= 0; i--) {
ans += bit.query(nums[i] - 1); //先查询
bit.update(nums[i]); //再更新
}
return ans;
}
};
int main() {
Solution a;
vector<int> test{7, 5, 6, 4};
cout << a.reversePairs(test) << endl;
return 0;
}
运行截图
