給定兩個大小為 m 和 n 的正序(從小到大)數組 nums1 和 nums2。請你找出并返回這兩個正序數組的中位數。
進階:你能設計一個時間復雜度為 O(log (m+n)) 的算法解決此問題嗎?
示例 1:
輸入:nums1 = [1,3], nums2 = [2]
輸出:2.00000
解釋:合并數組 = [1,2,3] ,中位數 2
示例 2:
輸入:nums1 = [1,2], nums2 = [3,4]
輸出:2.50000
解釋:合并數組 = [1,2,3,4] ,中位數 (2 + 3) / 2 = 2.5
直接將兩個數組賦值到一個新數組中,然后排序。
class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int n1=nums1.size(),n2=nums2.size();vector<int> nums3;for(int i=0;i<n1;i++) nums3.push_back(nums1[i]);for(int i=0;i<n2;i++) nums3.push_back(nums2[i]);sort(nums3.begin(),nums3.end());int s=(n1+n2)/2;double res;if((n1+n2)%2) res=1.0*nums3[s];else res=1.0*(nums3[s]+nums3[s-1])/2;return res;}
};
復雜度分析:
兩個有序數組合并最快的方法,時間復雜度: O((m + n)log(m+ n)), 這里m和n分別為數組nums1和nums2的長度,
空間復雜度: O(m+ n),存儲合并以后的數組,需要m+ n這么多空間。
(注:此方法來自于力扣官方題解)
class Solution {
public:int getKthElement(const vector<int>& nums1, const vector<int>& nums2, int k) {/* 主要思路:要找到第 k (k>1) 小的元素,那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 進行比較* 這里的 "/" 表示整除* nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共計 k/2-1 個* nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共計 k/2-1 個* 取 pivot = min(pivot1, pivot2),兩個數組中小于等于 pivot 的元素共計不會超過 (k/2-1) + (k/2-1) <= k-2 個* 這樣 pivot 本身最大也只能是第 k-1 小的元素* 如果 pivot = pivot1,那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把這些元素全部 "刪除",剩下的作為新的 nums1 數組* 如果 pivot = pivot2,那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把這些元素全部 "刪除",剩下的作為新的 nums2 數組* 由于我們 "刪除" 了一些元素(這些元素都比第 k 小的元素要小),因此需要修改 k 的值,減去刪除的數的個數*/int m = nums1.size();int n = nums2.size();int index1 = 0, index2 = 0;while (true) {// 邊界情況if (index1 == m) {return nums2[index2 + k - 1];}if (index2 == n) {return nums1[index1 + k - 1];}if (k == 1) {return min(nums1[index1], nums2[index2]);}// 正常情況int newIndex1 = min(index1 + k / 2 - 1, m - 1);int newIndex2 = min(index2 + k / 2 - 1, n - 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) {int totalLength = nums1.size() + nums2.size();if (totalLength % 2 == 1) {return getKthElement(nums1, nums2, (totalLength + 1) / 2);}else {return (getKthElement(nums1, nums2, totalLength / 2) + getKthElement(nums1, nums2, totalLength / 2 + 1)) / 2.0;}}
};
復雜度分析
時間復雜度:O(log(m+n)),其中 m 和 n 分別是數組 nums1 和 nums2 的長度。初始時有 k=(m+n)/2 或k=(m+n)/2+1,每一輪循環可以將查找范圍減少一半,因此時間復雜度是O(log(m+n))。
空間復雜度:O(1)。
版权声明:本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。
工作时间:8:00-18:00
客服电话
电子邮件
admin@qq.com
扫码二维码
获取最新动态