题目描述
493. Reverse Pairs
Given an array nums
, we call (i, j)
an important reverse pair if i < j
and nums[i] > 2*nums[j]
.
You need to return the number of important reverse pairs in the given array.
Example1:
Input: [1,3,2,3,1]
Output: 2
Example2:
Input: [2,4,3,5,1]
Output: 3
Note:
- The length of the given array will not exceed
50,000
. - All the numbers in the input array are in the range of 32-bit integer.
题意:给一个数组,让我们找出所有的重要逆序对个数.
重要逆序对指的是i < j
并且nums[i] > 2 * nums[j]
的逆序对。
算法1
(线段树) $O(nlogn)$
题解:这题的本质还是在让我们求逆序对,我们还是可以沿用Leetcode315题的树状数组算法 逆序对个数 ,只不过我们在进行区间求和的时候,假设nums[k]
离散化后的值是k
,那么我们求的不是sumRange[0:k - 1]
,而是找到小于nums[i]/2
的最大的nums[j]
离散化后的$k_1$,求解$sumRange(0:k_1)$。
首先我们使用一个数组存储每个离散化后的值出现的次数,再使用一个树状数组来执行区间求和和单点更新。
基于上述思想我们可以得到如下算法:
- 将
nums
数组进行离散化。 - 使用
hash
存储nums[i]
和离散化后值的对应关系 - 使用
half_hash
存储nums[i]
和满足2 * nums[j] < nums[i]
的最大nums[j]
离散化后值对应关系,这一步我们可以使用二分查找来解决。 - 我们从后往前遍历
nums
数组,将树状数组tree[0:half_hash[nums[i]]]
的区间和加入到答案中,同时将hash[nums[i]]
的值更新加1。
时间复杂度分析:二分查找和树状数组的时间复杂度都是$O(nlogn)$。
C++ 代码
class Solution {
public:
int n,m;
vector<int> tree;
inline int lowbit(int x)
{
return x & -x;
}
void update(int idx,int delta)
{
while(idx <= n)
{
tree[idx] += delta;
idx += lowbit(idx);
}
}
int rangeSum(int idx)
{
int res = 0;
while(idx > 0)
{
res += tree[idx];
idx -= lowbit(idx);
}
return res;
}
int reversePairs(vector<int>& nums) {
n = nums.size();
vector<long long> temp(n);
for(int i = 0 ; i < n ; i ++)
temp[i] = nums[i];
// 离散化
sort(temp.begin(),temp.end());
unordered_map<long long,int> hash,half_hash;
temp.erase(unique(temp.begin(),temp.end()),temp.end());
m = temp.size();
tree = vector<int>(n + 1,0);
// 求出每个数离散化后的值和满足2倍关系最大值离散化后的值
for(int i = 0 ; i < m ; i ++)
{
hash[temp[i]] = i + 1;
int l = 0,r = m - 1;
while(l < r)
{
int mid = (l + r + 1) >> 1;
if(temp[i] > 2 * temp[mid])
l = mid;
else
r = mid - 1;
}
if(temp[i] > 2 * temp[l])
half_hash[temp[i]] = l + 1;
else
half_hash[temp[i]] = 0;
}
long long res = 0;
// 从后往前遍历数组执行区间求和和单点更新
for(int i = n - 1 ; i >= 0 ; i --)
{
res += rangeSum(half_hash[nums[i]]);
update(hash[nums[i]],1);
}
return res;
}
};