当前位置: 代码迷 >> 综合 >> [leetcode] 4. Median of Two Sorted Arrays
  详细解决方案

[leetcode] 4. Median of Two Sorted Arrays

热度:63   发布时间:2024-01-05 01:15:37.0

原题

思路一:题目要求O(log (m+n))复杂度,一开始想到的是(m+n),遂试了下,发现居然也过了。。
新建一个数组,排序保存两个数组中的元素(mid+1)个,没有什么难度,防越界,注意奇偶数。

class Solution
{
public:double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2){int l1 = nums1.size();int l2 = nums2.size();vector<int> num3;int mid = (l1 + l2) / 2;int i = 0, j = 0;for (int k = 0; k < mid + 1; k++){if (i < l1 && (j >= l2 || nums1[i] < nums2[j])){num3.push_back(nums1[i++]);}else{num3.push_back(nums2[j++]);}}if ((l1 + l2) % 2 != 0){return (double)num3[mid];}else{return (double)(num3[mid] + num3[mid - 1]) / 2;}};
};

思路二:O(log (m+n))复杂度,一开始没有思路,查了资料发现一般都是使用分治法二分搜索

这个链接分析的非常清楚,学习到了!