剑指 Offer 51. 数组中的逆序对
本问题对应的 leetcode 原文链接：剑指 Offer 51. 数组中的逆序对
具体对应打卡问题看这里：【排序算法运用】剑指 Offer 51. 数组中的逆序对
问题描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例1 :
输入: [7,5,6,4]
输出: 5
限制:
0 <= 数组长度 <= 50000
解题思路
视频讲解直达： 本题视频讲解
代码实现
class Solution {
public int reversePairs(int[] nums) {
if(nums == null || nums.length <= 1){
return 0;
}
return mergeSort(nums, 0, nums.length - 1);
}
int mergeSort(int[] nums, int left, int right){
if(left >= right){
return 0;
}
int mid = (right - left) / 2 + left;
int x1 = mergeSort(nums, left, mid);
int x2 = mergeSort(nums, mid + 1, right);
int x3 = merge(nums, left, mid, mid+1, right);
return x1 + x2 + x3;
}
int merge(int[] nums, int l1, int r1, int l2, int r2){
int[] temp = new int[r2 - l1 + 1];
int count = 0;
int i = l1, j = l2, k = 0;
while(i <= r1 && j <= r2){
if(nums[i] > nums[j]){
count = count + (l2 - i);
temp[k++] = nums[j++];
}else{
temp[k++] = nums[i++];
}
}
while(i <= r1) temp[k++] = nums[i++];
while(j <= r2) temp[k++] = nums[j++];
// 把临时数组复制回原数组
k = 0;
for(i = l1; i <= r2; i++){
nums[i] = temp[k++];
}
return count;
}
}
复杂度和归并排序一样
时间：O(nlogn)
空间:O(n)