c++-c++编程基础之leetcode题解第4题寻找两个正序数组的中位数.zip

共1个文件

md：1个

编程语言

leetcode

需积分: 1 14 浏览量 2024-03-18 04:59:03 上传评论收藏 8KB ZIP 举报

资源推荐

资源详情

资源评论

收起资源包目录

c++_c++编程基础之leetcode题解第4题寻找两个正序数组的中位数.zip （1个子文件）

c++_c++编程基础之leetcode题解第4题寻找两个正序数组的中位数

README.md 58KB

# [4. Median of Two Sorted Arrays (Hard)](https://leetcode.com/problems/median-of-two-sorted-arrays) Given two sorted arrays <code>nums1</code> and <code>nums2</code> of size <code>m</code> and <code>n</code> respectively, return the median of the two sorted arrays. The overall run time complexity should be <code>O(log (m+n))</code>.   Example 1: <pre> Input: nums1 = [1,3], nums2 = [2] Output: 2.00000 Explanation: merged array = [1,2,3] and median is 2. </pre> Example 2: <pre> Input: nums1 = [1,2], nums2 = [3,4] Output: 2.50000 Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5. </pre>   Constraints: <ul> <li><code>nums1.length == m</code></li> <li><code>nums2.length == n</code></li> <li><code>0 <= m <= 1000</code></li> <li><code>0 <= n <= 1000</code></li> <li><code>1 <= m + n <= 2000</code></li> <li><code>-106 <= nums1[i], nums2[i] <= 106</code></li> </ul> **Companies**: [Amazon](https://leetcode.com/company/amazon), [Google](https://leetcode.com/company/google), [Adobe](https://leetcode.com/company/adobe), [Bloomberg](https://leetcode.com/company/bloomberg), [Apple](https://leetcode.com/company/apple), [Facebook](https://leetcode.com/company/facebook), [Yahoo](https://leetcode.com/company/yahoo), [Goldman Sachs](https://leetcode.com/company/goldman-sachs), [Microsoft](https://leetcode.com/company/microsoft), [TikTok](https://leetcode.com/company/tiktok), [Uber](https://leetcode.com/company/uber), [MathWorks](https://leetcode.com/company/mathworks), [Accenture](https://leetcode.com/company/accenture), [VMware](https://leetcode.com/company/vmware), [LinkedIn](https://leetcode.com/company/linkedin), [ServiceNow](https://leetcode.com/company/servicenow), [tcs](https://leetcode.com/company/tcs), [Walmart Labs](https://leetcode.com/company/walmart-labs), [PayPal](https://leetcode.com/company/paypal), [Oracle](https://leetcode.com/company/oracle), [Morgan Stanley](https://leetcode.com/company/morgan-stanley), [Samsung](https://leetcode.com/company/samsung), [Yandex](https://leetcode.com/company/yandex), [SAP](https://leetcode.com/company/sap), [Arcesium](https://leetcode.com/company/arcesium), [Sprinklr](https://leetcode.com/company/sprinklr), [Zoho](https://leetcode.com/company/zoho), [Capgemini](https://leetcode.com/company/capgemini), [OLX](https://leetcode.com/company/olx), [Zenefits](https://leetcode.com/company/zenefits), [Dropbox](https://leetcode.com/company/dropbox) **Related Topics**: [Array](https://leetcode.com/tag/array), [Binary Search](https://leetcode.com/tag/binary-search), [Divide and Conquer](https://leetcode.com/tag/divide-and-conquer) **Similar Questions**: * [Median of a Row Wise Sorted Matrix (Medium)](https://leetcode.com/problems/median-of-a-row-wise-sorted-matrix) ## Solution 1. ```cpp // OJ: https://leetcode.com/problems/median-of-two-sorted-arrays // Author: github.com/lzl124631x // Time: O(M + N) // Space: O(1) class Solution { public: double findMedianSortedArrays(vector<int>& A, vector<int>& B) { int M = A.size(), N = B.size(), a = 0, b = 0; auto getMin = [&]() { int ans; if (b >= N || (a < M && A[a] <= B[b])) ans = A[a++]; else ans = B[b++]; return ans; }; for (int i = 0; i < (M + N - 1) / 2; ++i) getMin(); if ((M + N) % 2) return getMin(); return (getMin() + getMin()) / 2.; } }; ``` ## Solution 2. <h4 id="intuition-1">Intuition</h4> Because the inputs are sorted arrays and the problem asks for a logarithmic time limit, we strongly feel that binary search (or a similar approach) is a promising method. While we're not sure how to cast the same pattern as a normal binary search on this problem, let's go over some steps of a regular binary search and see if we can get any inspiration. (If you are not familiar with binary search, you can refer to our <a href="https://leetcode.com/explore/learn/card/binary-search/" target="_blank">Binary Search Explore Card</a>) Here we use binary search to find <code>target</code> in a sorted array <code>A</code>: <ul> <li> Locate the middle index (element) of <code>A</code>. </li> <li> Compare the value of the middle element with <code>target</code>. </li> <li> Reduce the search space by cutting the current array in half and discarding the half which is guaranteed not to contain <code>target</code>. </li> <li> Repeat the above process until we either empty the array (move to half a the length of 0) or find <code>target</code>. </li> </ul> <img src="https://leetcode.com/problems/median-of-two-sorted-arrays/Figures/4/bs.png" alt="img"> At each step, the search space is cut in half, so we can quickly get the result. Now back to this problem where we have two sorted arrays. For the sake of convenience, let's call them <code>A</code> and <code>B</code>. <img src="https://leetcode.com/problems/median-of-two-sorted-arrays/Figures/4/2.png" alt="img"> Similarly, we can get and compare their middle values <code>A_mid</code> and <code>B_mid</code>. Without loss of generality in this example we assume <code>A_mid <= B_mid</code> initially, as shown in the yellow boxes. <img src="https://leetcode.com/problems/median-of-two-sorted-arrays/Figures/4/3.png" alt="img"> What does this comparison imply? It implies that we can compare sections of <code>A</code> and <code>B</code>. <blockquote> For the rest of this article, we will use ≤\le≤ to represent the relative magnitude of values in arrays. For example, Aleft≤ArightA_{\text{left}} \le A_{\text{right}}Aleft≤Aright</sp

评论收藏

内容反馈