leetcode上第四道題，如下。

給定兩個大小為 m 和 n 的有序數組?nums1 和?nums2。請你找出這兩個有序數組的中位數，并且要求算法的時間復雜度為?O(log(m + n))。你可以假設?nums1?和?nums2?不會同時為空。

?題目很簡潔，首先要搞懂中位數的概念，這玩意和平均數是有差別的。一開始我就搞錯了，把中位數和平均數搞混了，結果做了半天結果越來越離譜。百度的中位數概念如下：

中位數是按順序排列的一組數據中居于中間位置的數，即在這組數據中，有一半的數據比他大，有一半的數據比他小。

?如果序列個數為奇數，則中間的數就是中位數，只有一個，如果個數為偶數的話，則中位數是中間兩位數的均值，需要找到兩個數求平均值，如果個數為奇數,其中位數為（（n+1）/2）== （（n+2）/2），對于偶數，中位數為分別為（（n+2）/2）和（n/2），其中偶數情況下N/2 == (N+1)/2，因此不論奇數還是偶數，我們都可以求（（n+2）/2和（（n+1）/2），然后取平均值。

如果沒有時間復雜度要求的話很簡單，倆數組重排列后取中位數即可，但是題目要求是時間復雜度為O(log(m + n))。網上的同志說看到時間復雜度為log的基本上都是二分法，這個我之前不知道，水平不夠高。看了一位大神的解法，明白了。這道題可以這樣來看，求倆有序數組的中位數，相當于在一個有序的數組里找到第K個數，假設數組A的起始搜索位置和數組B的起始搜索位置分別是i和j，如果起始位置大于數組長度的話，說明在當前數組已經沒有數了，這時候直接去另一個數組里取第K個數即可。如果K為1的話，返回倆數組中第一個值當中的最小值即可，如果是其它情況，我們對K進行二分，先找到K/2，假設K' = K/2，找到則排除一半，再在找另一半即可，首先判斷起始位置加上要找的數長度是否超過數組長度，如果超過的話，這時候另外一個數組（假設為B）里前K' 個數是可以省略的，因為我們要找第K個數，那么它絕對不會在B的K‘ 里面，因為長度不夠。舉個例子，數組A={1}，數組B={0，2，4，6，7，8，9，12}，一共9個數，假設是有序數組，我們知道第五個數就是中位數，這里我們先二分K，5/2取余 = 2，數組A和B的初始查找位置都為0，對于A而言，2大于它的長度1，這時候我們可以排除掉數組B中的前兩個元素了，因為第五個數肯定要在前兩個數后面，這時候我們就排除掉兩個，這時候需要移動B的起始位置，j = j + K'，剩下三個，同樣的道理，對三進行二分。還有一種情況是兩個數組里從各自的起始位置都存在K‘個數，這時候就需要比較A[ i + K' ]和B[ j + K' ]，哪個大則移動另外一個數組的起始指針K’ 位，相等則移動任意一個。這時候就排除了K‘，我們只需要遞歸查找第K - K'，同理，繼續二分，K’ = (K - K') / 2; 直到K = 1，或者某個數組起始位置超出數組長度，這時候直接返回另一個數組里對應K‘即實我們要找的值。

總的來說，思路很巧妙，沒有經過訓練很難短時間內想到。此外就是二分法通常都需要遞歸調用。

下面是該問題的C代碼實現。

#define MIN(a,b) ((a) > (b) ? (b) : (a))int GetKth(int *nums1, int nums1Size, int start1, int *nums2, int nums2Size, int start2, int k) {int K1, K2;if (start1 + 1 > nums1Size)return nums2[start2 + k - 1];if (start2 + 1 > nums2Size)return nums1[start1 + k - 1];if (k == 1)return MIN(nums1[start1], nums2[start2]);if (start1 + k / 2 > nums1Size)return GetKth(nums1, nums1Size, start1, nums2, nums2Size, start2 + k / 2, k - k / 2);if (start2 + k / 2 > nums2Size)return GetKth(nums1, nums1Size, start1 + k / 2, nums2, nums2Size, start2, k - k / 2);K1 = nums1[start1 + k / 2 - 1];K2 = nums2[start2 + k / 2 - 1];if (K1 < K2)return GetKth(nums1, nums1Size, start1 + k / 2, nums2, nums2Size, start2, k - k / 2);elsereturn GetKth(nums1, nums1Size, start1, nums2, nums2Size, start2 + k / 2, k - k / 2); }double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){int k1 = (nums1Size + nums2Size + 1)/2;int k2 = (nums1Size + nums2Size + 2)/2;//奇數和偶數一樣return ((double)GetKth(nums1, nums1Size, 0, nums2, nums2Size, 0, k1) + (double)GetKth(nums1, nums1Size, 0, nums2, nums2Size, 0, k2))/2; }

參考目錄：

1.?https://www.cnblogs.com/grandyang/p/4465932.html

=============================================================================================

Linux應用程序、內核、驅動、后臺開發交流討論群(745510310)，感興趣的同學可以加群討論、交流、資料查找等，前進的道路上，你不是一個人奧^_^。
?

總結

以上是生活随笔為你收集整理的leetcode 4. 寻找两个有序数组的中位数，c语言的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。