51. 数组中的逆序对

---

comments: true
difficulty: 困难
edit_url: https://github.com/doocs/leetcode/edit/main/lcof/%E9%9D%A2%E8%AF%95%E9%A2%9851.%20%E6%95%B0%E7%BB%84%E4%B8%AD%E7%9A%84%E9%80%86%E5%BA%8F%E5%AF%B9/README.md

面试题 51. 数组中的逆序对

题目描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

 

示例 1:

输入: [7,5,6,4]
输出: 5

 

限制：

0 <= 数组长度 <= 50000

解法

方法一：归并排序

归并排序的过程中，如果左边的数大于右边的数，则右边的数与 左边的数之后的数 都构成逆序对。

时间复杂度 $O(n\times \log n)$，空间复杂度 $O(n)$。其中 $n$ 为数组长度。

Python3

class Solution:def reversePairs(self, nums: List[int]) -> int:def merge_sort(l, r):if l >= r:return 0mid = (l + r) >> 1ans = merge_sort(l, mid) + merge_sort(mid + 1, r) #对左右子序列进行递归排序，#以下为merge操作：先两个两个排序归并，再四个四个排序归并，，，tmp = [] # 合并后的结果序列i, j = l, mid + 1 # 左，右子序列的指针while i <= mid and j <= r:if nums[i] <= nums[j]: #1.如果左子序列的元素小于等于右子序列的元素，将左子序列的元素添加到结果序列中tmp.append(nums[i])i += 1 #2.左子序列指针向后移动一位else:ans += mid - i + 1 #核心：如果左边的数大于右边的数，则右边的数与 左边的数之后的数 都构成逆序对tmp.append(nums[j]) #3.否则，将右子序列的元素添加到结果序列中j += 1 #4.右子序列指针向后移动一位# 将剩余的元素直接添加到结果序列中     tmp.extend(nums[i : mid + 1])tmp.extend(nums[j : r + 1])nums[l : r + 1] = tmpreturn ansreturn merge_sort(0, len(nums) - 1)

Java

class Solution {private int[] nums;private int[] t;public int reversePairs(int[] nums) {this.nums = nums;int n = nums.length;this.t = new int[n];return mergeSort(0, n - 1);}private int mergeSort(int l, int r) {if (l >= r) {return 0;}int mid = (l + r) >> 1;int ans = mergeSort(l, mid) + mergeSort(mid + 1, r);int i = l, j = mid + 1, k = 0;while (i <= mid && j <= r) {if (nums[i] <= nums[j]) {t[k++] = nums[i++];} else {ans += mid - i + 1;t[k++] = nums[j++];}}while (i <= mid) {t[k++] = nums[i++];}while (j <= r) {t[k++] = nums[j++];}for (i = l; i <= r; ++i) {nums[i] = t[i - l];}return ans;}
}

C++

class Solution {
public:int reversePairs(vector<int>& nums) {int n = nums.size();if (n == 0) {return 0;}int t[n];function<int(int, int)> mergeSort = [&](int l, int r) -> int {if (l >= r) {return 0;}int mid = (l + r) >> 1;int ans = mergeSort(l, mid) + mergeSort(mid + 1, r);int i = l, j = mid + 1, k = 0;while (i <= mid && j <= r) {if (nums[i] <= nums[j]) {t[k++] = nums[i++];} else {ans += mid - i + 1;t[k++] = nums[j++];}}while (i <= mid) {t[k++] = nums[i++];}while (j <= r) {t[k++] = nums[j++];}for (i = l; i <= r; ++i) {nums[i] = t[i - l];}return ans;};return mergeSort(0, n - 1);}
};

Go

func reversePairs(nums []int) int {n := len(nums)t := make([]int, n)var mergeSort func(l, r int) intmergeSort = func(l, r int) int {if l >= r {return 0}mid := (l + r) >> 1ans := mergeSort(l, mid) + mergeSort(mid+1, r)i, j, k := l, mid+1, 0for i <= mid && j <= r {if nums[i] <= nums[j] {t[k] = nums[i]k, i = k+1, i+1} else {ans += mid - i + 1t[k] = nums[j]k, j = k+1, j+1}}for ; i <= mid; i, k = i+1, k+1 {t[k] = nums[i]}for ; j <= r; j, k = j+1, k+1 {t[k] = nums[j]}for i = l; i <= r; i++ {nums[i] = t[i-l]}return ans}return mergeSort(0, n-1)
}

TypeScript

function reversePairs(nums: number[]): number {const mergeSort = (l: number, r: number): number => {if (l >= r) {return 0;}const mid = (l + r) >> 1;let ans = mergeSort(l, mid) + mergeSort(mid + 1, r);let i = l;let j = mid + 1;const t: number[] = [];while (i <= mid && j <= r) {if (nums[i] <= nums[j]) {t.push(nums[i++]);} else {ans += mid - i + 1;t.push(nums[j++]);}}while (i <= mid) {t.push(nums[i++]);}while (j <= r) {t.push(nums[j++]);}for (i = l; i <= r; ++i) {nums[i] = t[i - l];}return ans;};return mergeSort(0, nums.length - 1);
}

JavaScript

/*** @param {number[]} nums* @return {number}*/
var reversePairs = function (nums) {const mergeSort = (l, r) => {if (l >= r) {return 0;}const mid = (l + r) >> 1;let ans = mergeSort(l, mid) + mergeSort(mid + 1, r);let i = l;let j = mid + 1;let t = [];while (i <= mid && j <= r) {if (nums[i] <= nums[j]) {t.push(nums[i++]);} else {ans += mid - i + 1;t.push(nums[j++]);}}while (i <= mid) {t.push(nums[i++]);}while (j <= r) {t.push(nums[j++]);}for (i = l; i <= r; ++i) {nums[i] = t[i - l];}return ans;};return mergeSort(0, nums.length - 1);
};

C#

public class Solution {private int[] nums;private int[] t;public int ReversePairs(int[] nums) {this.nums = nums;int n = nums.Length;this.t = new int[n];return mergeSort(0, n - 1);}private int mergeSort(int l, int r) {if (l >= r) {return 0;}int mid = (l + r) >> 1;int ans = mergeSort(l, mid) + mergeSort(mid + 1, r);int i = l, j = mid + 1, k = 0;while (i <= mid && j <= r) {if (nums[i] <= nums[j]) {t[k++] = nums[i++];} else {ans += mid - i + 1;t[k++] = nums[j++];}}while (i <= mid) {t[k++] = nums[i++];}while (j <= r) {t[k++] = nums[j++];}for (i = l; i <= r; ++i) {nums[i] = t[i - l];}return ans;}
}

Swift

class Solution {private var nums: [Int] = []private var temp: [Int] = []func reversePairs(_ nums: [Int]) -> Int {self.nums = numslet n = nums.countself.temp = [Int](repeating: 0, count: n)return mergeSort(0, n - 1)}private func mergeSort(_ left: Int, _ right: Int) -> Int {if left >= right {return 0}let mid = (left + right) / 2var count = mergeSort(left, mid) + mergeSort(mid + 1, right)var i = leftvar j = mid + 1var k = leftwhile i <= mid && j <= right {if nums[i] <= nums[j] {temp[k] = nums[i]i += 1} else {count += mid - i + 1temp[k] = nums[j]j += 1}k += 1}while i <= mid {temp[k] = nums[i]i += 1k += 1}while j <= right {temp[k] = nums[j]j += 1k += 1}for i in left...right {nums[i] = temp[i]}return count}
}