东莞万江网站制作,河北省建设注册中心网站首页,科技成果鉴定机构,wordpress 主题 宠物题目描述
给定两个大小分别为 m 和 n 的正序#xff08;从小到大#xff09;数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (mn)) 。
示例 1#xff1a;
输入#xff1a;nums1 [1,3], nums2 [2]
输出#xff1a;2.0…题目描述
给定两个大小分别为 m 和 n 的正序从小到大数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (mn)) 。
示例 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提示
nums1.length mnums2.length n0 m 10000 n 10001 m n 2000-106 nums1[i], nums2[i] 106
AC代码
class Solution {
public:double findMedianSortedArrays(vectorint nums1, vectorint nums2) {double ans;vectordouble num(2002);int m nums1.size(), n nums2.size(), m1 0, n1 0;int len m n;for (int i 0; i len / 2; i) {if (n1 n) {num[i] nums1[m1];m1;}else if (m1 m) {num[i] nums2[n1];n1;}else{num[i] (nums1[m1] nums2[n1]) ? nums2[n1] : nums1[m1];if (nums1[m1] nums2[n1]) n1;else m1;}if ((m1 n1) (len / 2 1)) break;}if (len % 2) ans num[len/2];else ans (num[len/2-1] num[len/2]) / 2.0;return ans;}
};
