LeetCode刷题笔记：剑指Offer51.数组中的逆序对

1. 问题描述

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

2. 解题思路

归并排序，在合并的时候，当左边的大于右边，就计算逆序数。

3. 代码实现

class Solution {
int count = 0;
public int reversePairs(int[] nums) {
int len = nums.length;
mergeSort(nums, 0, len - 1);
return count;
}
private void mergeSort(int[] nums, int left, int right) {
int len = nums.length;
if (left >= right) {
return;
}
int mid = (right - left) / 2 + left;
// 拆分
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
// 合并
merge(nums, left, mid, right);
}
private void merge(int[] nums, int left, int mid, int right) {
int len = nums.length;
int[] temp = new int[right - left + 1];
int i = left;
int j = mid + 1;
int t = 0;
while (i <= mid && j <= right) {
if (nums[i] <= nums[j]) {
temp[t++] = nums[i++];
} else {
count += mid - i + 1;
temp[t++] = nums[j++];
}
}
while (i <= mid) {
temp[t++] = nums[i++];
}
while (j <= right) {
temp[t++] = nums[j++];
}
// 覆盖原数组
for (int k = 0; k < temp.length; k++) {
nums[left + k] = temp[k];
}
}
}

最后

以上就是伶俐路人为你收集整理的LeetCode刷题笔记：剑指Offer51.数组中的逆序对的全部内容，希望文章能够帮你解决LeetCode刷题笔记：剑指Offer51.数组中的逆序对所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。