<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                合規國際互聯網加速 OSASE為企業客戶提供高速穩定SD-WAN國際加速解決方案。 廣告
                # 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">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span><span class="hljs-params">(object)</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">reversePairs</span><span class="hljs-params">(self, nums)</span>:</span> n = len(nums) cnt = <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n): <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(i + <span class="hljs-params">1</span>, n): <span class="hljs-keyword">if</span> nums[i] > <span class="hljs-params">2</span> * nums[j]: cnt += <span class="hljs-params">1</span> <span class="hljs-keyword">return</span> 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 = <span class="hljs-params">0</span> <span class="hljs-keyword">while</span> l < len(left) <span class="hljs-keyword">and</span> r < len(right): <span class="hljs-keyword">if</span> left[l] <= <span class="hljs-params">2</span> * right[r]: l += <span class="hljs-params">1</span> <span class="hljs-keyword">else</span>: self.cnt += len(left) - l r += <span class="hljs-params">1</span> ``` ``` ### 代碼 代碼支持:Python3 Python3 Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span><span class="hljs-params">(object)</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">reversePairs</span><span class="hljs-params">(self, nums)</span>:</span> self.cnt = <span class="hljs-params">0</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">mergeSort</span><span class="hljs-params">(lst)</span>:</span> L = len(lst) <span class="hljs-keyword">if</span> L <= <span class="hljs-params">1</span>: <span class="hljs-keyword">return</span> lst <span class="hljs-keyword">return</span> mergeTwo(mergeSort(lst[:L//<span class="hljs-params">2</span>]), mergeSort(lst[L//<span class="hljs-params">2</span>:])) <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">mergeTwo</span><span class="hljs-params">(left, right)</span>:</span> l = r = <span class="hljs-params">0</span> <span class="hljs-keyword">while</span> l < len(left) <span class="hljs-keyword">and</span> r < len(right): <span class="hljs-keyword">if</span> left[l] <= <span class="hljs-params">2</span> * right[r]: l += <span class="hljs-params">1</span> <span class="hljs-keyword">else</span>: self.cnt += len(left) - l r += <span class="hljs-params">1</span> <span class="hljs-keyword">return</span> sorted(left+right) mergeSort(nums) <span class="hljs-keyword">return</span> 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)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看