<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國際加速解決方案。 廣告
                # 0004. 尋找兩個正序數組的中位數 ## 題目地址(4. 尋找兩個正序數組的中位數) <https://leetcode-cn.com/problems/median-of-two-sorted-arrays/> ## 題目描述 ``` <pre class="calibre18">``` 給定兩個大小為 m 和 n 的正序(從小到大)數組 nums1 和 nums2。 請你找出這兩個正序數組的中位數,并且要求算法的時間復雜度為 O(log(m + n))。 你可以假設 nums1 和 nums2 不會同時為空。 示例 1: nums1 = [1, 3] nums2 = [2] 則中位數是 2.0 示例 2: nums1 = [1, 2] nums2 = [3, 4] 則中位數是 (2 + 3)/2 = 2.5 ``` ``` ## 前置知識 - 中位數 - 分治法 - 二分查找 ## 公司 - 阿里 - 百度 - 騰訊 ## 思路 首先了解一下 Median 的概念,一個數組中 median 就是把數組分成左右等分的中位數。 如下圖: ![](https://img.kancloud.cn/97/7d/977df88111934cac41b23138c78d951c_1328x528.jpg) 這道題,很容易想到暴力解法,時間復雜度和空間復雜度都是`O(m+n)`, 不符合題中給出`O(log(m+n))`時間復雜度的要求。 我們可以從簡單的解法入手,試了一下,暴力解法也是可以被 Leetcode Accept 的. 分析中會給出兩種解法,暴力求解和二分解法。 #### 解法一 - 暴力 (Brute Force) 暴力解主要是要 merge 兩個排序的數組`(A,B)`成一個排序的數組。 用兩個`pointer(i,j)`,`i` 從數組`A`起始位置開始,即`i=0`開始,`j` 從數組`B`起始位置, 即`j=0`開始. 一一比較 `A[i] 和 B[j]`, 1. 如果`A[i] <= B[j]`, 則把`A[i]` 放入新的數組中,i 往后移一位,即 `i+1`. 2. 如果`A[i] > B[j]`, 則把`B[j]` 放入新的數組中,j 往后移一位,即 `j+1`. 3. 重復步驟#1 和 #2,直到`i`移到`A`最后,或者`j`移到`B`最后。 4. 如果`j`移動到`B`數組最后,那么直接把剩下的所有`A`依次放入新的數組中. 5. 如果`i`移動到`A`數組最后,那么直接把剩下的所有`B`依次放入新的數組中. Merge 的過程如下圖。 ![](https://img.kancloud.cn/96/ca/96ca54aed5cf57ed48672d8956731838_850x1186.jpg) *時間復雜度: `O(m+n) - m is length of A, n is length of B`* *空間復雜度: `O(m+n)`* #### 解法二 - 二分查找 (Binary Search) 由于題中給出的數組都是排好序的,在排好序的數組中查找很容易想到可以用二分查找(Binary Search), 這里對數組長度小的做二分, 保證數組 A 和 數組 B 做 partition 之后 `len(Aleft)+len(Bleft)=(m+n+1)/2 - m是數組A的長度, n是數組B的長度` 對數組 A 的做 partition 的位置是區間`[0,m]` 如圖: ![](https://img.kancloud.cn/6c/e7/6ce70104ced99f4783e5da34411ce4d0_679x1186.jpg) 下圖給出幾種不同情況的例子(注意但左邊或者右邊沒有元素的時候,左邊用`INF_MIN`,右邊用`INF_MAX`表示左右的元素: ![](https://img.kancloud.cn/8c/a0/8ca0f14a72469479b0b1f8c5cee2b0ee_1586x922.jpg) 下圖給出具體做的 partition 解題的例子步驟, ![](https://img.kancloud.cn/f9/82/f982876debceee42247a3cdc56673b10_950x1186.jpg) *時間復雜度: `O(log(min(m, n)) - m is length of A, n is length of B`* *空間復雜度: `O(1)` - 這里沒有用額外的空間* ## 關鍵點分析 1. 暴力求解,在線性時間內 merge 兩個排好序的數組成一個數組。 2. 二分查找,關鍵點在于 3. 要 partition 兩個排好序的數組成左右兩等份,partition 需要滿足`len(Aleft)+len(Bleft)=(m+n+1)/2 - m是數組A的長度, n是數組B的長度` 4. 并且 partition 后 A 左邊最大(`maxLeftA`), A 右邊最小(`minRightA`), B 左邊最大(`maxLeftB`), B 右邊最小(`minRightB`) 滿足 `(maxLeftA <= minRightB && maxLeftB <= minRightA)` 有了這兩個條件,那么 median 就在這四個數中,根據奇數或者是偶數, ``` <pre class="calibre18">``` 奇數: median = max(maxLeftA, maxLeftB) 偶數: median = (max(maxLeftA, maxLeftB) + min(minRightA, minRightB)) / 2 ``` ``` ## 代碼 代碼支持: Java,JS: Java Code: *解法一 - 暴力解法(Brute force)* ```java \[\] class MedianTwoSortedArrayBruteForce { public double findMedianSortedArrays(int\[\] nums1, int\[\] nums2) { int\[\] newArr = mergeTwoSortedArray(nums1, nums2); int n = newArr.length; if (n % 2 == 0) { // even return (double) (newArr\[n / 2\] + newArr\[n / 2 - 1\]) / 2; } else { // odd return (double) newArr\[n / 2\]; } } private int\[\] mergeTwoSortedArray(int\[\] nums1, int\[\] nums2) { int m = nums1.length; int n = nums2.length; int\[\] res = new int\[m + n\]; int i = 0; int j = 0; int idx = 0; while (i < m && j < n) { if (nums1\[i\] <= nums2\[j\]) { res\[idx++\] = nums1\[i++\]; } else { res\[idx++\] = nums2\[j++\]; } } while (i < m) { res\[idx++\] = nums1\[i++\]; } while (j < n) { res\[idx++\] = nums2\[j++\]; } return res; } } ``` <pre class="calibre18">``` ```javascript [] /** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number} */ var findMedianSortedArrays = function (nums1, nums2) { // 歸并排序 const merged = []; let i = 0; let j = 0; while (i < nums1.length && j < nums2.length) { if (nums1[i] < nums2[j]) { merged.push(nums1[i++]); } else { merged.push(nums2[j++]); } } while (i < nums1.length) { merged.push(nums1[i++]); } while (j < nums2.length) { merged.push(nums2[j++]); } const { length } = merged; return length % 2 === 1 ? merged[Math.floor(length / 2)] : (merged[length / 2] + merged[length / 2 - 1]) / 2; }; ``` ``` **復雜度分析** - 時間復雜度:O(max(m,n))O(max(m, n))O(max(m,n)) - 空間復雜度:O(m+n)O(m + n)O(m+n) *解法二 - 二分查找(Binary Search)* ```js \[\] /\*\* - 二分解法 - @param {number\[\]} nums1 - @param {number\[\]} nums2 - @return {number} \*/ var findMedianSortedArrays = function (nums1, nums2) { // make sure to do binary search for shorten array if (nums1.length > nums2.length) { \[nums1, nums2\] = \[nums2, nums1\]; } const m = nums1.length; const n = nums2.length; let low = 0; let high = m; while (low <= high) { const i = low + Math.floor((high - low) / 2); const j = Math.floor((m + n + 1) / 2) - i; const maxLeftA = i === 0 ? -Infinity : nums1\[i - 1\]; const minRightA = i === m ? Infinity : nums1\[i\]; const maxLeftB = j === 0 ? -Infinity : nums2\[j - 1\]; const minRightB = j === n ? Infinity : nums2\[j\]; if (maxLeftA <= minRightB && minRightA >= maxLeftB) { return (m + n) % 2 === 1 ``` <pre class="calibre18">``` ? Math.max(maxLeftA, maxLeftB) : (Math.max(maxLeftA, maxLeftB) + Math.min(minRightA, minRightB)) / 2; ``` ``` } else if (maxLeftA > minRightB) { high = i - 1; } else { low = low + 1; } } }; ``` ```java \[\] class MedianSortedTwoArrayBinarySearch { public static double findMedianSortedArraysBinarySearch(int\[\] nums1, int\[\] nums2) { // do binary search for shorter length array, make sure time complexity log(min(m,n)). if (nums1.length > nums2.length) { return findMedianSortedArraysBinarySearch(nums2, nums1); } int m = nums1.length; int n = nums2.length; int lo = 0; int hi = m; while (lo <= hi) { // partition A position i int i = lo + (hi - lo) / 2; // partition B position j int j = (m + n + 1) / 2 - i; ``` <pre class="calibre18">``` int maxLeftA = i == 0 ? Integer.MIN_VALUE : nums1[i - 1]; int minRightA = i == m ? Integer.MAX_VALUE : nums1[i]; int maxLeftB = j == 0 ? Integer.MIN_VALUE : nums2[j - 1]; int minRightB = j == n ? Integer.MAX_VALUE : nums2[j]; if (maxLeftA <= minRightB && maxLeftB <= minRightA) { // total length is even if ((m + n) % 2 == 0) { return (double) (Math.max(maxLeftA, maxLeftB) + Math.min(minRightA, minRightB)) / 2; } else { // total length is odd return (double) Math.max(maxLeftA, maxLeftB); } } else if (maxLeftA > minRightB) { // binary search left half hi = i - 1; } else { // binary search right half lo = i + 1; } } return 0.0; } ``` ``` } ``` **復雜度分析** - 時間復雜度:O(log(min(m,n)))O(log(min(m, n)))O(log(min(m,n))) - 空間復雜度:O(log(min(m,n)))O(log(min(m, n)))O(log(min(m,n))) 大家對此有何看法,歡迎給我留言,我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫:<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg) ![](https://img.kancloud.cn/77/1d/771d6f53e2a51febbcb6fa97f2899ac3_1586x578.jpg)
                  <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>

                              哎呀哎呀视频在线观看