一、概述：

? ? ?這道題思路其實(shí)蠻簡(jiǎn)單的，就是邊界太難考慮了，所以一直沒(méi)能通過(guò)，寫(xiě)了好長(zhǎng)的代碼考慮邊界，然后看到一個(gè)大神寫(xiě)的代碼：

https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/c-er-fen-cha-zhao-by-da-li-wang/?。簡(jiǎn)直是嘆為天人，敬佩不已，發(fā)現(xiàn)自己走的路還很長(zhǎng)。

二、思路：

? ? 由于是兩個(gè)排序的數(shù)組，只要兩個(gè)數(shù)組的間距為保持為總長(zhǎng)的一半，二分遍歷較短的數(shù)組，然后通過(guò)一半思路去求另一個(gè)數(shù)組的位置，比較數(shù)組的左邊是否小于另一數(shù)組當(dāng)前節(jié)點(diǎn)，如果是，找到中位數(shù)的位置。

? ?特別需要注意的是，在較長(zhǎng)的數(shù)組上一定存在一個(gè)中位數(shù)。

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {if (nums1.size() > nums2.size())return findMedianSortedArrays(nums2, nums1);int M = nums1.size();int N = nums2.size();int l = 0;int r = M;while (l <= r) {int mid = (r - l) / 2 + l;int rightPos = (N + M) / 2 - mid;int max1 = (mid - 1 >= 0) ? nums1[mid - 1] : INT_MIN;int min1 = (mid < M) ? nums1[mid] : INT_MAX;int max2 = (rightPos - 1 >= 0) ? nums2[rightPos - 1] : INT_MIN;int min2 = (rightPos < N) ? nums2[rightPos] : INT_MAX;if (max1 > min2) { //如果num1[mid]左邊的數(shù)大于右邊指向的數(shù),中位數(shù)左移r = mid - 1;}else if (max2 > min1) { //如果num1[mid]右邊的數(shù)大于左邊指向的數(shù)，中位數(shù)右移l = mid + 1;}else {l = r = mid;break;}}int u = l; //指向nums1對(duì)應(yīng)的中位數(shù)位置int v = (M + N) / 2 - l; //指向中位數(shù)右邊對(duì)應(yīng)中位數(shù)的位置int low = max(u - 1 >= 0 ? nums1[u - 1] : INT_MIN,v - 1 >= 0 ? nums2[v - 1] : INT_MIN);int high = min(u < M ? nums1[u] : INT_MAX,v < N ? nums2[v] : INT_MAX);if ((N + M) % 2 == 1)return high;return float(low + high) / 2; }

?

總結(jié)

以上是生活随笔為你收集整理的leetcode C++ 4. 寻找两个有序数组的中位数 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。 请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。