[TOC]
思路
首先我们一般一开始都用的暴力查找后面符合性质的点的个数,但是我么发现时间复杂度O(N^2)会超时 所以我们要进行优化,在我们查找第i个点的时候 第j个点位满足性质的点 如果i-j之间有大于i的数 那么j也就是k的满足性质的点 所以如果一个序列有序 对于正数的序列 那么翻转对一定是0 而对于负数要做特定 所以我们需要一个有序序列和另一个有序序列 进行查找 =>归并排序的思路 然后我们在合并两个有序序列即二路归并时进行筛选一下就可以啦 特别要注意q[i]<=q[j]时 负数有可能满足性质 而且要注意指针一定 因为i一定是i 如果这时候满足 我们还要继续j向后探索一下 对于i这个点是否还有 然后对于q[i]>q[j] 如果满足大于二倍 直接+=mid-i+1 如果不满足 因为要j 我们无法判断后面的是否满足 所以这时候我们也需要探索i之后的点 就行 两种情况
思路简单 但情况容易忽略
讲述看到这一题的思路
解题方法
归并排序
复杂度
时间复杂度:
添加时间复杂度, 示例: o(nlog2)
空间复杂度:
添加空间复杂度, 示例: $O(nlogn)$
Code
```Java []
class Solution {
//不能写成statici因为 只有PUBLIC CLASS MAIN在每次测试样例才重新加载static
int res=0;
static int[] tmp=new int[50010];
public int reversePairs(int[] nums) {
//和逆序对是一样的
//如果我们用暴力搜索的思路就是 对每一个数向后探索 是否
// 但是n2 方 有重复的 就是如果在 i j
//之间 有个数比i要大 k那么整个 k j 也是一个逆序对
// 所以我们要对序列每一个有序区间分别开来进行求
// 也就是归并的思想 因为 归并就是把原来的序列按照原来的位置
// 划分位多个有序的序列 此时每一个序列是有序 所以逆序对0
// 但是他们合并的时候 只需要考虑前面区间就行了
merge_sory(nums,0,nums.length-1);
return res;
}
public void merge_sory(int[] q,int l,int r){
if(l>=r){
return ;
}
int mid=l+r>>1;
merge_sory(q,l,mid);
merge_sory(q,mid+1,r);
int k=0,i=l,j=mid+1;
while(i<=mid&&j<=r){
if(q[i]<q[j]){
if(q[i]>2*(long)q[j]){
int m=j;
while(m+1<=r&&q[i]>2*(long)q[m+1]) m++;
res+=m+1-j;
tmp[k++]=q[i++];
}
else{
tmp[k++]=q[i++];
}
}
else if(q[i]==q[j]){
if(q[i]>2*(long)q[j]){
int m=j;
while(m+1<=r&&q[i]>2*(long)q[m+1]) m++;
res+=m+1-j;
tmp[k++]=q[i++];
}
else{
tmp[k++]=q[i++];
}
}
else {
if(q[i]>2*(long)q[j]) res+=mid-i+1;
else{
int m=i;
while(m+1<=mid&&q[m+1]<=2*(long)q[j]) m++;
res+=mid-m;
}
tmp[k++]=q[j++];
}
}
System.out.print(res+" ");
while(i<=mid) tmp[k++]=q[i++];
while(j<=r) tmp[k++]=q[j++];
for(i=l,j=0;i<=r;i++,j++) q[i]=tmp[j];
}
}
```