【問題描述】面試題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
  
  

#####計數關鍵

時間復雜度：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;// 自頂向下的歸并排序實現 2public 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; 整形溢出，應該像下面這樣計算 midint 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));} }

參考網站：https://liweiwei1419.gitee.io/leetcode-algo/leetcode-by-tag/sorting-algorithm/merge-sorting.html#%E4%BC%98%E5%8C%96%E7%9A%84%E5%AE%9E%E7%8E%B0

總結

以上是生活随笔為你收集整理的[剑指offer][JAVA]面试题[51][数组中的逆序对][归并排序]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。