題目描述

• 多說無益～直接沖代碼吧！
  

思路 && 代碼

1. 暴力 O($n^2$)

• 乍一看這題目，很難不直接用暴力法沖一沖（也就雙層循環的事）
• 但是不出意料地超時啦～想一想，O($n^2$)會超時，那么我們就試著思考怎么降低時間復雜度到O(nlogn)吧！（還是不行的話，就再去思考O(n)的方法，循序漸進～）
• 于是，分治的思路就躍然于紙上了～

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

2. 歸并排序法（分治O(nlogn））

• 總體框架應該是和歸并排序一樣的
• 從頭思考，如果采用分治的方法進行二分，需要有怎樣的考慮？
• 當前遞歸層的結果，首先應該是左半邊內部的結果 + 右半邊內部的結果
• 然后，應該再對左半邊與右半邊的聯系進行處理
• 為什么要排序？
• 首先，我們通過二分遞歸的形式，占用了O(logn)的復雜度
• 然后，我們需要使用剩下的O(n)復雜度，完成剩下的步驟
• 而排序，占用了O(n)復雜度，同時實現了剩下的步驟
• 左半邊排序、右半邊排序后，并不會影響左右半邊直接的聯系，也就是無后效性
• 合并操作：
• 維護 lowIndex，用于記錄插入左半邊值后，新增的逆序對。
• 插入左半邊值后，增加的逆序對 = 已經插入的右邊值個數
• 注意：左半邊當前值、右半邊當前值相同的情況，選擇插入左半邊當前值，這是為了保證正確性。（可以寫個例子考慮一下就知道原因了～）

class Solution {public int reversePairs(int[] nums) {return mergeSort(nums, 0, nums.length - 1);}public int mergeSort(int[] nums, int left, int right) {if(left >= right) {return 0;}// 1. 二分，先獲取【合并前局部逆序對】總數int mid = (left + right) / 2;int res = mergeSort(nums, left, mid) + mergeSort(nums, mid + 1, right);// 2. 合并處理int i = left, j = mid + 1;int[] arr = new int[right - left + 1];// 用于處理相等情況int lowIndex = 0;for(int k = 0; k < arr.length; k++) {if(i > mid){arr[k] = nums[j++];}else if(j > right || nums[i] <= nums[j]) {res += lowIndex;arr[k] = nums[i++];}else if(nums[i] > nums[j]){lowIndex++;arr[k] = nums[j++];}}// 把排序數組賦予原數組for(i = left; i <= right; i++) {nums[i] = arr[i - left];}return res;} }

二刷

• 歸并排序的思想可太能套用了！

class Solution {// 歸并排序public int reversePairs(int[] nums) {return mergeSort(nums, 0, nums.length - 1);}int mergeSort(int[] nums, int left, int right) {if(left >= right) {return 0;}int mid = (left + right) / 2;int res = mergeSort(nums, left, mid) + mergeSort(nums, mid + 1, right);int[] arr = new int[right - left + 1];int first = left, second = mid + 1;for(int i = 0; i < arr.length; i++) {if(first > mid) {arr[i] = nums[second++];}else if(second > right || nums[first] <= nums[second]) {arr[i] = nums[first++];res += second - mid - 1;}else if(nums[second] < nums[first]) {arr[i] = nums[second++];}}for(int i = 0; i < arr.length; i++) {nums[left + i] = arr[i];}return res;} }

總結

以上是生活随笔為你收集整理的【LeetCode笔记】剑指Offer 51. 数组中的逆序对（Java、分治）的全部內容，希望文章能夠幫你解決所遇到的問題。

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