数组的逆序对
2021-05-05 10:30
标签：逆序 net for nbsp n+1 com 从后往前 归并 内存 题目描述来自力扣https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/ 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。 除了暴力法以外，还有两种更优的方法可以解决这个问题。 1）第一种方法： 进行归并排序时，假设已经回溯到最后一次合并，如上图所示。 1、两个子数组进行一轮比较后，右边数组指针指向红色标记处。此时，对于lp指向的元素来说，存在两个逆序对（和）。 2、进行第二轮比较后，lp此时指向12，rp指向右边数组的尾后位置。这是，对于元素12来说，逆序对个数为4。 依次类推，可以得到最终答案。当然，在递归最深处往前回溯时，会自动记录各个不同消息子数组的逆序对个数。具体代码如下： 时间复杂度：O(nlgn), 空间复杂度：O(n) 2)第二种方法： 基本原理比较好理解。现在来说一下如何利用树状数组减少内存的使用。树状数组用来存在原始数组的前缀和。其更新和查询的时间复杂度均为O(lgn)，n为数组大小。 实际上，树状数组只需要存储原始数组每个元素大小的排名即可。这样一来，树状数组的尺寸可以设为原始数组的大小加1（设原始数组有n个元素，则数状数组大小为n+1。因为数组数组第0位不存储元素）。 代码如下： PS: 树状数组的基本原理和实现可以参考以下链接 https://blog.csdn.net/flushhip/article/details/79165701 https://www.cnblogs.com/xenny/p/9739600.html 数组的逆序对 标签：逆序 net for nbsp n+1 com 从后往前 归并 内存 原文地址：https://www.cnblogs.com/chenqn/p/13192423.html
7 12 15 16 | 4 6 9 10
^ ^ ^
lp rp rpint reversePairs(vectorint>& nums) {
int n = nums.size();
vectorint> temp(n);
return mergeAndCount(nums, temp, 0, n - 1);
}
int mergeAndCount(vectorint>& nums, vectorint>& temp, int lo, int hi)
{
if(lo >= hi) return 0;
int mid = lo + (hi - lo) / 2;
int ans = 0;
ans += mergeAndCount(nums, temp, lo, mid) + mergeAndCount(nums,temp, mid + 1, hi);
if(nums[mid] 1])
{
return ans;
}
int pos = lo;
int i = lo;
int j = mid + 1;
while(i hi)
{
if(nums[i] nums[j])
{
temp[pos++] = nums[i++];
ans += j - mid - 1;
}
else
{
temp[pos++] = nums[j++];
}
}
for(int k = i; k k)
{
temp[pos++] = nums[k];
ans += j - mid - 1;
}
for(int k = j; k k)
{
temp[pos++] = nums[k];
}
std::copy(temp.begin() + lo, temp.begin() + hi + 1, nums.begin() + lo);
return ans;
}
struct TreeArray
{
TreeArray(int cap) : data(cap + 1), n(cap) {}
//从整数的二进制表达来看，此函数用来计算整数x的最低`1`比特位到x的最低比特位组成的整数
static int lowbit(int x)
{
return x & (-x);
}
//查询并返回原始数组a[1...i]的和
int query(int i)
{
int res = 0;
while(i > 0)
{
res += data[i];
i -= lowbit(i);
}
return res;
}
//更新树状数组
void update(int i, int val)
{
while(i n)
{
data[i] += val;
i += lowbit(i);
}
}
private:
int n;
vectorint> data;
};
class Solution {
public:
int reversePairs(vectorint>& nums) {
int n = nums.size();
vectorint> temp = nums;
std::sort(temp.begin(), temp.end());
for(auto& num : nums)
{
num = lower_bound(temp.begin(), temp.end(), num) - temp.begin() + 1;
}
TreeArray ta(n);
int ans = 0;
for(int i = n - 1; i >= 0; --i)
{
ans += ta.query(nums[i] - 1);
ta.update(nums[i], 1);
}
return ans;
}
};