【问题描述】面试题51.数组中的逆序对 （困难）
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4]
输出: 5
限制：
0 <= 数组长度 <= 50000
【解答思路】
1. 暴力 超时
- 枚举所有数组
-符合条件累加
时间复杂度：O(N^2) 空间复杂度：O(1)
public int reversePairs(int[] nums) {
int n = nums.length;
int count = 0 ;
if(n == 0){
return 0;
}
for(int i = 0 ; i< n-1;i++){
for(int j = i+1 ;j < n ;j++){
if(nums[i]>nums[j]){
count++;
}
}
}
return count;
}
2. 归并排序
-
合并1 前面有四个树比1大 总数+4
计数关键
count = mid - i -1
时间复杂度：O(NlogN) 空间复杂度：O(N)
public int reversePairs(int[] nums) {
int len = nums.length;
if(len <2 ){
return 0;
}
int[] copy = new int[len];
for (int i = 0; i < len ; i++) {
copy[i] = nums[i];
}
int[] temp = new int[len];
//引入temp[] 为了避免每次合并时需要创建、销毁新的数组，避免下标问题
return reversePairs(copy, 0 ,len - 1, temp);
}
/**
*
* @param nums
* @param left
* @param right
* @param temp
* @return
*/
private int reversePairs(int[] nums, int left, int right, int[] temp) {
if(left == right){
return 0;
}
//防止溢出
int mid = left + (right- left) /2;
int leftPairs = reversePairs(nums, left, mid , temp);
int rightPairs = reversePairs(nums, mid+1, right, temp);
//优化归并排序
if(nums[mid] <= nums[mid+1]){
return leftPairs + rightPairs;
}
int crossPairs = mergeAndCount(nums, left, mid ,right, temp);
return leftPairs + rightPairs + crossPairs;
}
/**
*
* @param nums
* @param left
* @param mid
* @param right
* @param temp
* @return
*/
private int mergeAndCount(int[] nums, int left, int mid, int right, int[] temp) {
//区间复制到temp[]数组
for (int i = left; i <=right ; i++) {
temp[i] = nums[i];
}
int i = left ;
int j = mid+1;
int count = 0 ;
for (int k = left; k <= right ; k++) {
//前半部分遍历完
if(i == mid+1){
nums[k] = temp[j];
j++;
}//后半部分遍历完
else if(j == right+1){
nums[k] = temp[i];
i++;
}
//count计数 逻辑（else if -else ） <= 稳定性
else if(temp[i]<=temp[j]){
nums[k] = temp[i];
i++;
}else {
nums[k] = temp[j];
j++;
count += (mid-i+1);
}
}
return count;
}
【总结】
1. 归并排序思想
2. 归并排序优化
if(nums[mid] <= nums[mid+1]){
return leftPairs + rightPairs;
}
3. 规避排序模板
import java.util.Arrays;
public class MergeSort2 {
// 用于合并两个有序数组的辅助数组，使用它是为了避免每次归并都重复开辟空间
// 它的长度，就是数组的长度，每次只用它的一部分，直到最后一次归并，使用它的全部
private int[] temp;
// 自顶向下的归并排序实现 2
public void sort(int[] arr) {
int len = arr.length;
temp = new int[len];
mergeSort(arr, 0, len - 1);
}
private void mergeSort(int[] arr, int left, int right) {
// 修复1：为了防止计算 int mid = (left + right) / 2; 整形溢出，应该像下面这样计算 mid
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// 优化2：如果 arr 数组已经前后有序（前面数组中的最后一个元素不大于后面数组中的第 1 个元素）
if (arr[mid] <= arr[mid + 1]) {
return;
}
mergeOfTwoSortArray(arr, left, mid, right);
}
private void mergeOfTwoSortArray(int[] arr, int left, int mid, int right) {
// 优化3：使用一个全局的辅助数组，避免每次都开辟新的内存空间去优化，这样做反而编程实现更简单，不用考虑索引的偏移
for (int i = left; i <= right; i++) { // 闭区间，所以 right 这个索引也要赋值
temp[i] = arr[i];
}
// temp 的 [left,mid] 有序
// temp 的 [mid+1,right] 有序，现在要将它们整理成有序，放回 arr 中，一个一个放就好了
int i = left;
int j = mid + 1;
for (int k = left; k <= right; k++) {
// i 用完
if (i > mid) {
arr[k] = temp[j];
j++;
} else if (j > right) { // j 用完
arr[k] = temp[i];
i++;
} else if (temp[i] < temp[j]) {
arr[k] = temp[i];
i++;
} else {
arr[k] = temp[j];
j++;
}
}
}
public static void main(String[] args) {
int[] nums = {8, 4, 3, 6, 5, 1};
MergeSort2 mergeSort2 = new MergeSort2();
mergeSort2.sort(nums);
System.out.println(Arrays.toString(nums));
}
}
image.png
