南昌做网站设计,自助建设网站,在wordpress中设置mx记录,黑龙江网站建设巨耀网络题目
寻找两个正序数组的中位数 给定两个大小分别为 m 和 n 的正序#xff08;从小到大#xff09;数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。 算法的时间复杂度应该为 O(log (mn)) 。 示例 1#xff1a; 输入#xff1a;nums1 [1,3], nums2 [2] 输…题目
寻找两个正序数组的中位数 给定两个大小分别为 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
2023年3月13号的解法
class Solution { public: double findMedianSortedArrays(vector nums1, vector nums2) { const int Len nums1.size() nums2.size(); const int iAvg1 Rec(nums1.data(), nums1.data() nums1.size(), nums2.data(), nums2.data() nums2.size(), (Len - 1) / 2); if (Len 1) { return iAvg1; } const int iAvg2 Rec(nums1.data(), nums1.data() nums1.size(), nums2.data(), nums2.data() nums2.size(), (Len - 1) / 21); return (iAvg1 iAvg2) / 2.0; } int Rec(int* b1, int* e1, int* b2, int* e2, int iFindIndex) { if (b1 e1) { return b2[iFindIndex]; } if (b2 e2) { return b1[iFindIndex]; } if (0 iFindIndex) { return min(*b1, *b2); } int k (iFindIndex 1) / 2; const int index1 min(k - 1,(int)( e1 - b1)-1); const int index2 min(k - 1, (int)(e2 - b2 )- 1); if (b1[index1] b2[index2]) { return Rec(b1 index1 1, e1, b2, e2, iFindIndex - index1 - 1); } return Rec(b1, e1, b2 index2 1, e2, iFindIndex - index2 - 1); } };
2023年8月6号的解法
class Solution { public: double findMedianSortedArrays(vector nums1, vector nums2) { m_c nums1.size() nums2.size(); m_iHalf m_c / 2; int left 0, r min(m_iHalf, (int)nums1.size()) 1;//左闭右开 while (r left 1) { const auto mid left (r - left) / 2; const int leftLen2 m_iHalf - mid; const int iRet Cmp(mid, leftLen2, nums1, nums2); if (0 iRet) { break; } else if (iRet 0) { r mid; } else { left mid; } } if (m_dRet 0 ) { Cmp(left,m_iHalf-left,nums1,nums2); } return m_dRet; } int Cmp(int leftLen1, int leftLen2, const vector nums1, const vector nums2) { if (leftLen2 nums2.size()) { return 1; } int iLeftMax INT_MIN; if (leftLen1 0) { iLeftMax max(iLeftMax, nums1[leftLen1 - 1]); } if (leftLen2 0) { iLeftMax max(iLeftMax, nums2[leftLen2 - 1]); } int iRightMin INT_MAX; if (leftLen1 nums1.size()) { iRightMin min(iRightMin, nums1[leftLen1]); } if (leftLen2 nums2.size()) { iRightMin min(iRightMin, nums2[leftLen2]); } if (iLeftMax iRightMin) { if (1 m_c) { m_dRet iRightMin; } else { m_dRet (iLeftMax iRightMin) / 2.0; } return 0; } if ((leftLen1 0) (nums1[leftLen1 - 1] iRightMin)) { return-1; } return 1; } double m_dRet-1; int m_c; int m_iHalf; };
其它
视频课程
如果你觉得复杂想从简单的算法开始可以学习我的视频课程。 https://edu.csdn.net/course/detail/38771 我的其它课程 https://edu.csdn.net/lecturer/6176
测试环境
win7 VS2019 C17
相关下载
doc版文档排版好 https://download.csdn.net/download/he_zhidan/88348653
