LeetCode 寻找两个有序数组的中位数

 题目描述

给定两个大小为 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

题目分析

该题主要是对时间复杂度的要求，实现起来要充分利用题中的已经知道两个数组有序这一条件，进行解答。设置两个指针i，j;分别指向数组1和数组2的首元素，比较他们的大小，按照从小到大的顺序加入到新的数组中。因为两个数组有序，因此需要做的工作的就是从开始的i,j分别指向的第一个元素开始，将小的加入到新数组中，并将指针向后移动，不断的比较i,j指向的元素，那个指针指向的 元素小就将其加入到新数组中，对应的指针向后移动。实际上就是在对两个数组进行合并排序。

注意这里的结束条件，就是并不需要将两个数组完全的合并起来，因为只需要我们合并到能确定中位数即可。

// ConsoleApplication4.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。 // #include<iostream> #include<string> #include<vector> using namespace std; double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2); int main() { vector<int> n1 = {2,3}; vector<int> n2 = {}; double m = findMedianSortedArrays(n1, n2); cout << m; return 0; } double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int Middle_index = (nums1.size() + nums2.size()) / 2; vector<int> com; if (nums1.size() == 0) { return nums2.size() % 2 == 0?(double)(nums2[Middle_index - 1]+ nums2[Middle_index])/2: nums2[Middle_index]; } if (nums2.size() == 0) { return nums1.size() % 2 == 0?(double)(nums1[Middle_index - 1] + nums1[Middle_index])/2: nums1[Middle_index]; } for (int i = 0, j = 0; com.size() <= Middle_index;) { while (i < nums1.size()&& j < nums2.size()) { if (nums1[i] <= nums2[j]) { com.push_back(nums1[i]); i++; } else { com.push_back(nums2[j]); j++; } } if (i == nums1.size()&&j!= nums2.size()) { com.push_back(nums2[j]); j++; } if (j == nums2.size()&&i!=nums1.size()) { com.push_back(nums1[i]); i++; } } double median; if ((nums1.size() + nums2.size()) % 2 == 0) { median =(double)(com[Middle_index - 1] + com[Middle_index])/2; return median; } else { median = com[Middle_index]; return median; } }

 执行耗费时间还可以。