数据结构算法（数组中的逆序对）

剑指 Offer 51. 数组中的逆序对

LeetCode题目链接：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4]
输出: 5
限制：
0 <= 数组长度 <= 50000

解题思路： 最朴素解法，暴力解法，遍历所有的数据对，前者大于后者就是一组逆序对

class Solution { public int reversePairs(int[] nums) { int res = 0; for(int i = 0;i<nums.length;i++){ for(int j =i+1;j<nums.length;j++) if(nums[i]>nums[j]) res++; } return res; } } 

由于时间复杂度O(n^2)的，超出时间限制。

数组的长度限制是50000，对于一个O(n^2)的时间复杂度，数据规模达到25亿大小。所以使用归并排序来解决，逆序对问题也是归并排序的应用。

class Solution { private int res = 0; public int reversePairs(int[] nums) { int[] temp = new int[nums.length]; res = 0; sort(nums, 0, nums.length - 1, temp); return res; } private void sort(int[] arr, int l, int r, int[] temp) { if (l >= r) return; int mid = (r - l) / 2 + l; sort(arr, l, mid, temp); sort(arr, mid + 1, r, temp); if (arr[mid] > arr[mid + 1]) merge(arr, l, mid, r, temp); } private void merge(int[] arr, int l, int mid, int r, int[] temp) { System.arraycopy(arr, l, temp, l, r - l + 1); int i = l; int j = mid + 1; for (int k = l; k <= r; k++) { if (i > mid) { arr[k] = temp[j]; j++; } else if (j > r) { arr[k] = temp[i]; i++; } else if (temp[i] <= temp[j]) { arr[k] = temp[i]; i++; } else { res += mid - i + 1; arr[k] = temp[j]; j++; } } } public static void main(String[] args) { int[] arr = {7, 5, 6, 4}; int n = new Solution().reversePairs(arr); System.out.println(n); } } 

改进代码范式，不设置res成员变量，直接用函数返回值将结果返回，使用函数式编程，减少需要维护的状态。

 class Solution { public int reversePairs(int[] nums) { int[] temp = new int[nums.length]; int res = sort(nums, 0, nums.length - 1, temp); return res; } private int sort(int[] arr, int l, int r, int[] temp) { if (l >= r) return 0; int res = 0; int mid = (r - l) / 2 + l; res += sort(arr, l, mid, temp); res += sort(arr, mid + 1, r, temp); if (arr[mid] > arr[mid + 1]) res += merge(arr, l, mid, r, temp); return res; } private int merge(int[] arr, int l, int mid, int r, int[] temp) { System.arraycopy(arr, l, temp, l, r - l + 1); int i = l; int j = mid + 1; int res = 0; for (int k = l; k <= r; k++) { if (i > mid) { arr[k] = temp[j]; j++; } else if (j > r) { arr[k] = temp[i]; i++; } else if (temp[i] <= temp[j]) { arr[k] = temp[i]; i++; } else { res += mid - i + 1; arr[k] = temp[j]; j++; } } return res; } public static void main(String[] args) { int[] arr = {7, 5, 6, 4}; int n = new Solution().reversePairs(arr); System.out.println(n); } } 

提交结果

本文地址：https://blog.csdn.net/wankcn/article/details/108030249