C/C++描述 LeetCode 4. 尋找兩個正序陣列的中位數
??大家好，我叫亓官劼（qí guān jié ），在CSDN中記錄學習的點滴歷程，時光荏苒，未來可期，加油~博主目前僅在CSDN中寫博客，唯一博客更新的地址為：亓官劼的博客
本文原創為亓官劼，請大家支持原創，部分平臺一直在惡意盜取博主的文章！！！
給定兩個大小為 m 和 n 的正序（從小到大）陣列 nums1 和 nums2，
請你找出這兩個正序陣列的中位數，并且要求演算法的時間復雜度為 O(log(m + n))，
你可以假設 nums1 和 nums2 不會同時為空，
示例 1:
nums1 = [1, 3]
nums2 = [2]
則中位數是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
則中位數是 (2 + 3)/2 = 2.5
題解
題目中要求演算法的時間復雜度為$ O(log(m+n)) $,所以這里不能直接暴力，由于是已經排序好的兩個陣列，我們可以使用二分法，兩個陣列的二分這里我們可以再進行再一次的轉化，將尋找中位數轉化為尋找第k小的數，如果總長度為奇數，那么中位數就是第
(len+1)/2的數，如果總長度為偶數，那么中位數就為(len/2 + len/2+1) /2.0，然后我們使用這個思想進行演算法實作，
class Solution {
public:
int fintK(vector<int>& nums1, vector<int>& nums2, int k){
int len1 = nums1.size();
int len2 = nums2.size();
int index1 = 0;
int index2 = 0;
while(true){
// 當運行到右邊界時
if(index1 == len1){
// 回傳nums2當前index2+k個數
return nums2[index2 + k - 1];
}
if(index2 == len2){
return nums1[index1 + k - 1];
}
if(k == 1)
return min(nums1[index1],nums2[index2]);
int newIndex1 = min(index1 + k / 2 - 1, len1 - 1);
int newIndex2 = min(index2 + k / 2 - 1, len2 - 1);
int pivot1 = nums1[newIndex1];
int pivot2 = nums2[newIndex2];
if (pivot1 <= pivot2) {
k -= newIndex1 - index1 + 1;
index1 = newIndex1 + 1;
}
else {
k -= newIndex2 - index2 + 1;
index2 = newIndex2 + 1;
}
}
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
// 轉換為找第K小的數，當len為偶數時，找len/2 + len/2+1兩個數，當len為奇數時，找第len/2的數
int len = nums1.size() + nums2.size();
if(len%2 == 0){
//當len為偶數時，找第len/2 + len/2+1兩個數,中位數為兩個數/2.0
return ((fintK(nums1,nums2,len/2) + fintK(nums1,nums2,len/2+1) )/2.0 );
}else{
//當len為奇數時，找第(len+1)/2的數
return fintK(nums1,nums2,(len+1)/2);
}
}
};
亓官劼
CSDN認證博客專家
Python
全堆疊
資料結構與演算法
CSDN認證博客專家
Python
全堆疊
資料結構與演算法
大家好，我是亓官劼(qíguānjié)，在博客中分享資料結構與演算法、Python全堆疊開發、Java后端開發、前端、OJ題解及各類報錯資訊解決方案等經驗，一起加油，用知識改變命運，未來可期，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/70399.html
標籤：其他