找尋某一群 n 個排序好的數字的中位數在這題的定義即是
\(
median(a_1 … a_n) = \begin{cases}
a_{\left\lceil\frac{n}{2}\right\rceil} & \text{if n is odd} \\
\frac{a_\frac{n}{2} + a_{\frac{n}{2} + 1}}{2} & \text{if n is even}
\end{cases}
\)
接著這道題目就會變成如何找出兩個排序好的陣列的第 k 項,我們可以利用兩邊對 k 分半的方式去比較找出。
如果我要找出排序好的兩個陣列 a 和 b 合併後的第 k 項,那我就先找出兩邊陣列目前的第\( \frac{k}{2} \) 項。如果\( a_\frac{k}{2} < b_\frac{k}{2} \)則表示 a 的前 \( \frac{k}{2} \) 都比 b 的前 \( \frac{k}{2} \) 項小,則第 k 項絕不可能在這 a 的前 \( \frac{k}{2} \) 項中;反之亦然。(證明方式可以用反證,如果第 k 項會在這之中,表示至少要從 b 這邊拿 \( \frac{k}{2} \) 去補前面不夠的數量,但 b 的第 \( \frac{k}{2} \) 項比它大,故不足,所以不可能。)
排除掉 a 的前 \( \frac{k}{2} \) 項後,再找尋剩下的數字第 \( k – \frac{k}{2} \) 項即可,以此類推直到 a 陣列或 b 陣列沒有值,或是找到只剩一項為止。
參考解法:GoodTecher
C++(44ms)
/*******************************************************/ /* LeetCode 4. Median of Two Sorted Arrays */ /* Author: Maplewing [at] knightzone.studio */ /* Version: 2018/09/24 */ /*******************************************************/ #include <cstdlib> #include <climits> class Solution { public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int totalLength = nums1.size() + nums2.size(); if (totalLength % 2 == 1){ return findKthElement(nums1, 0, nums2, 0, totalLength / 2 + 1); } else{ return (findKthElement(nums1, 0, nums2, 0, totalLength / 2) + findKthElement(nums1, 0, nums2, 0, totalLength / 2 + 1)) / 2.0; } } double findKthElement(vector<int>& nums1, int start1, vector<int>& nums2, int start2, int k){ if (start1 >= nums1.size()){ return nums2[start2 + k - 1]; } if (start2 >= nums2.size()){ return nums1[start1 + k - 1]; } if(k == 1){ return min(nums1[start1], nums2[start2]); } int index1 = start1 + k / 2 - 1; int index2 = start2 + k / 2 - 1; int element1 = index1 < nums1.size() ? nums1[index1] : INT_MAX; int element2 = index2 < nums2.size() ? nums2[index2] : INT_MAX; if (element1 < element2){ return findKthElement(nums1, start1 + k / 2, nums2, start2, k - k / 2); } else{ return findKthElement(nums1, start1, nums2, start2 + k / 2, k - k / 2); } } };
回應