0493. 翻轉對 · ttttt

# 0493. 翻轉對 ## 題目地址（493. 翻轉對） <https://leetcode-cn.com/problems/reverse-pairs/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個數組 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我們就將 (i, j) 稱作一個重要翻轉對。你需要返回給定數組中的重要翻轉對的數量。示例 1: 輸入: [1,3,2,3,1] 輸出: 2 示例 2: 輸入: [2,4,3,5,1] 輸出: 3 注意: 給定數組的長度不會超過50000。輸入數組中的所有數字都在32位整數的表示范圍內。 ``` ``` ## 前置知識 - 歸并排序 - 逆序數 - 分治 ## 公司 - 阿里 - 百度 - 字節 ## 暴力法 ### 思路讀完這道題你應該就能聯想到逆序數才行。求解逆序數最簡單的做法是使用雙層循環暴力求解。我們仿照求解決逆序數的解法來解這道題（其實唯一的區別就是系數從 1 變成了 2）。 ### 代碼代碼支持：Python3 Python3 Code: ``` <pre class="calibre18">``` class Solution(object): def reversePairs(self, nums): n = len(nums) cnt = 0 for i in range(n): for j in range(i + 1, n): if nums[i] > 2 * nums[j]: cnt += 1 return cnt ``` ``` ## 分治法 ### 思路如果你能夠想到逆序數，那么你很可能直到使用類似歸并排序的方法可以求解逆序數。實際上逆序數只是歸并排序的副產物而已。我們在正常的歸并排序的代碼中去計算逆序數即可。由于每次分治的過程，左右兩段數組分別是有序的，因此我們可以減少一些運算。從時間復雜度的角度上講，我們從O(N2)O(N^2)O(N2)優化到了 O(NlogN)O(NlogN)O(NlogN)。具體來說，對兩段有序的數組，有序數組內部是不需要計算逆序數的。我們計算逆序數的邏輯只是計算兩個數組之間的逆序數，我們假設兩個數組是 A 和 B，并且 A 數組最大的元素不大于 B 數組最小的元素。而要做到這樣，我們只需要常規的歸并排序即可。接下來問題轉化為求解兩個有序數組之間的逆序數，并且兩個有序數組之間滿足關系`A數組最大的元素不大于B數組最小的元素`。關于計算逆序數的核心代碼(Python3): ``` <pre class="calibre18">``` l = r = 0 while l < len(left) and r < len(right): if left[l] <= 2 * right[r]: l += 1 else: self.cnt += len(left) - l r += 1 ``` ``` ### 代碼代碼支持：Python3 Python3 Code: ``` <pre class="calibre18">``` class Solution(object): def reversePairs(self, nums): self.cnt = 0 def mergeSort(lst): L = len(lst) if L <= 1: return lst return mergeTwo(mergeSort(lst[:L//2]), mergeSort(lst[L//2:])) def mergeTwo(left, right): l = r = 0 while l < len(left) and r < len(right): if left[l] <= 2 * right[r]: l += 1 else: self.cnt += len(left) - l r += 1 return sorted(left+right) mergeSort(nums) return self.cnt ``` ``` **復雜度分析** - 時間復雜度：O(NlogN)O(NlogN)O(NlogN) - 空間復雜度：O(logN)O(logN)O(logN) 大家對此有何看法，歡迎給我留言，我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。目前已經 37K star 啦。大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg) 對于具體的排序過程我們偷懶直接使用了語言內置的方法 sorted，這在很多時候是有用的，即使你是參加面試，這種方式通常也是允許的。省略非核心的考點，可以使得問題更加聚焦，這是一種解決問題的思路，在工作中也很有用。 ## 關鍵點解析 - 歸并排序 - 逆序數 - 分治 - 識別考點，其他非重點可以使用語言內置方法 ## 擴展這道題還有很多別的解法，感性的可以參考下這個題解 [General principles behind problems similar to "Reverse Pairs"](https://leetcode.com/problems/reverse-pairs/discuss/97268/General-principles-behind-problems-similar-to-%22Reverse-Pairs%22)