剑指 Offer 51. 数组中的逆序对
本问题对应的 leetcode 原文链接：剑指 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)
Python
class Solution(object):
def reversePairs(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums or len(nums) <= 1:
return 0
def mergeSort(left, right):
if left >= right:
return 0
mid = (right - left) // 2 + left
x1 = mergeSort(left, mid)
x2 = mergeSort(mid + 1, right)
i, j = left, mid + 1
temp = []
count = 0
while i <= mid and j <= right:
if nums[i] > nums[j]:
count += mid - i + 1
temp.append(nums[j])
j += 1
else:
temp.append(nums[i])
i += 1
while i <= mid:
temp.append(nums[i])
i += 1
while j <= right:
temp.append(nums[j])
j += 1
nums[left:right+1] = temp
return x1 + x2 + count
return mergeSort(0, len(nums) - 1)
C++
class Solution {
public:
int reversePairs(vector<int>& nums) {
if (nums.empty() || nums.size() <= 1)
return 0;
function<int(int, int)> mergeSort;
mergeSort = [&](int left, int right) -> int {
if (left >= right)
return 0;
int mid = left + (right - left) / 2;
int x1 = mergeSort(left, mid);
int x2 = mergeSort(mid + 1, right);
int i = left, j = mid + 1;
int count = 0;
vector<int> temp;
while (i <= mid && j <= right) {
if (nums[i] > nums[j]) {
count += mid - i + 1;
temp.push_back(nums[j]);
j++;
} else {
temp.push_back(nums[i]);
i++;
}
}
while (i <= mid) {
temp.push_back(nums[i]);
i++;
}
while (j <= right) {
temp.push_back(nums[j]);
j++;
}
for (int k = left; k <= right; k++) {
nums[k] = temp[k - left];
}
return x1 + x2 + count;
};
return mergeSort(0, nums.size() - 1);
}
};
Go
func reversePairs(nums []int) int {
if len(nums) == 0 || len(nums) == 1 {
return 0
}
var mergeSort func(int, int) int
mergeSort = func(left, right int) int {
if left >= right {
return 0
}
mid := left + (right - left) / 2
x1 := mergeSort(left, mid)
x2 := mergeSort(mid + 1, right)
i, j := left, mid + 1
count := 0
temp := make([]int, 0, right - left + 1)
for i <= mid && j <= right {
if nums[i] > nums[j] {
count += mid - i + 1
temp = append(temp, nums[j])
j++
} else {
temp = append(temp, nums[i])
i++
}
}
for i <= mid {
temp = append(temp, nums[i])
i++
}
for j <= right {
temp = append(temp, nums[j])
j++
}
copy(nums[left:right+1], temp)
return x1 + x2 + count
}
return mergeSort(0, len(nums) - 1)
}
JS
/**
* @param {number[]} nums
* @return {number}
*/
var reversePairs = function(nums) {
if (nums == null || nums.length <= 1) {
return 0;
}
return mergeSort(nums, 0, nums.length - 1);
};
function mergeSort(nums, left, right) {
if (left >= right) {
return 0;
}
let mid = Math.floor((right - left) / 2 + left);
let x1 = mergeSort(nums, left, mid);
let x2 = mergeSort(nums, mid + 1, right);
let x3 = merge(nums, left, mid, mid + 1, right);
return x1 + x2 + x3;
}
function merge(nums, l1, r1, l2, r2) {
let temp = new Array(r2 - l1 + 1);
let count = 0;
let 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;
}