题目描述
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(n^logn)$
题解:这题的本质还是在让我们求逆序对,我们还是可以沿用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)$。
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;
// 下面的二分查找等价于如下,满足`temp[t] * 2 < temp[i]`的最大值,这里需要使用double取保temp[i]无论奇偶数都是正确的
// half_hash[temp[i]] = lower_bound(temp.begin(),temp.end(),(double)temp[i] / 2) - temp.begin();
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;
}
};
算法2
(归并排序) $O(n^logn)$
题解2:分治。这里我们同样使用和Leetcode327题的归并排序的思想。merge_sort
的返回值是区间[lo,hi]
内部的所有满足条件的对。我们的算法如下,如果区间长度小于等于1,那么直接返回0。否则,我们首先递归求解两个子区间的答案,接下来我们再对两个子区间归并之前统计一下我们的答案。我们使用指针i
代表左半区间当前遍历到的元素,我们使用指针r
指向有半区间满足nums[r] * 2 < nums[i]
的最大的元素的下一个位置。那么右半区间满足nums[i] > nums[j] * 2
的元素个数就是r - mid - 1
。
这里我们继续分析一下这段操作的时间复杂度。因为左半区间已经是排好序的了,那么r
随着i
单调不递减的(类似于双指针算法)。所以i
只在区间[lo,mid]
中遍历一次,r
只在区间[mid + 1,hi]
中遍历一次。所以这段操作的时间复杂度就是$O(hi - lo)$的,这也恰好是我们执行归并排序的归并操作的时间复杂度。所以整个算法的时间复杂度也是和归并排序一样$O(nlogn)$的。
最后不要忘了将两个子数组归并,这里我直接使用inplace_merge
函数,这个函数的必须参数为inplace_merge( BidirIt first, BidirIt middle, BidirIt last )
含义为在原地对已经排好序的[first,mid)
和[mid,last)
的两个区间进行排序,函数内部实现的时候是申请了额外空间的。
对应的merge
函数的必须参数为merge( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2,OutputIt d_first )
。其含义为将排好序的[first1,last1)
和[first2,last2)
进行归并,并且把答案写在d_first
位置上。这里需要注意的是,input1
和input2
可以是同一个vector,也可以有重叠部分,但是output
不能是input1
和input2
其中的一个。$O(hi - lo)$
C++ 代码
class Solution {
public:
int reversePairs(vector<int>& nums) {
return merge_sort(nums,0,nums.size() - 1);
}
int merge_sort(vector<int>& nums,int lo,int hi)
{
if(lo >= hi) return 0;
int mid = (lo + hi) >> 1,res = 0,r = mid + 1;
res = merge_sort(nums,lo,mid) + merge_sort(nums,mid + 1,hi);
for(int i = lo ; i <= mid ; i ++)
{
while(r <= hi && nums[r] * 2ll < nums[i]) r ++;
res += (r - mid - 1);
}
inplace_merge(nums.begin() + lo,nums.begin() + mid + 1,nums.begin() + hi + 1);
return res;
}
};