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

共1个文件

md：1个

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

在本压缩包中，主题聚焦于C++编程基础与LeetCode算法题目的解析，特别是针对LeetCode中的第四题——寻找两个正序数组的中位数。这是一个经典的算法问题，旨在锻炼程序员对数组处理和排序算法的理解。下面我们将深入探讨这个问题及其解决方案。我们要了解什么是中位数。在一组有序数据中，中位数是将数据一分为二的数值，一半的数据小于或等于它，另一半数据大于或等于它。在两个正序数组中找中位数，我们需要合并这两个数组并找出中位数，但要求是尽可能地减少操作次数，因为这直接影响到算法的效率。 C++作为一门强大的编程语言，它提供了丰富的数据结构和算法工具来解决这类问题。对于这个问题，我们可以考虑以下几种策略： 1. 合并排序：最直观的方法是将两个数组合并成一个大数组，然后进行排序，找到中位数。但是这种方法的时间复杂度为O(n log n)，其中n是两个数组的元素总数，不满足高效要求。 2. 快速选择：可以利用快速选择或者快速排序的思想，找到两个数组的第(k1+k2)/2个元素（假设第一个数组有k1个元素，第二个数组有k2个元素）。但这种方法也需要辅助空间，且在最坏情况下仍可能达到O(n log n)的时间复杂度。 3. 二分查找法：这是更优的解决方案。由于题目要求数组都是正序的，我们可以利用二分查找的思想。首先确定一个可能的中位数，然后比较这个值与两个数组的对应位置的元素，调整中位数的位置。通过不断地缩小范围，最终找到中位数。这种方法的时间复杂度为O(log(min(m, n)))，其中m和n分别为两个数组的长度。在实现这个算法时，C++的关键点包括： 1. 数组操作：理解和熟练使用C++的数组和指针，包括动态数组（`std::vector`）和静态数组。 2. 二分查找：理解二分查找的逻辑，能够编写出递归或迭代的二分查找函数。 3. 边界条件处理：在处理数组边界时要特别小心，防止越界。 4. 优化技巧：为了提高效率，可以在比较过程中尽量减少不必要的比较，比如通过维护较小数组的长度，避免重复计算。 5. 中位数的特殊情况：当两个数组长度不相等时，中位数可能是两个数组的交界点，需要根据长度来确定。在LeetCode平台上，这个问题通常要求在线求解，所以还需要关注代码的空间复杂度，尽量减少额外空间的使用。通过学习和实践这个题目的解法，不仅可以提升C++编程能力，还能加深对数组操作、排序算法和二分查找的理解，对于准备面试和提升编程技能非常有帮助。解题过程和代码实现是学习的重要部分，你可以打开压缩包中的文件，详细查看代码实现和解释，以进一步理解这个问题的解决方案。

资源推荐

资源详情

资源评论

收起资源包目录

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

评论收藏

内容反馈