厦门 网站制作长沙3合1网站建设

1.实验内容

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

2.实验目的

算法的时间复杂度应该为 O(log (m+n)) 。

3.基本思路

碰到时间复杂度要求log的，肯定用二分查找，即每次在现有数据的一半中找，下一次再一半，每次循环可以将查找范围缩小一半。但是我这里用多的是双指针算法，一起查找，不需要归并数组，只需找到中位数的下标，但是复杂度仍然是O（min（m+n））

4.算法分析

首先需要通过判断`m`和`n`的大小来确定两个数组是否为空。

如果两个数组都不为空，则使用双指针法遍历两个数组，将较小的元素依次添加到动态数组`temp`中，直到找到第k+1小的元素为止。

如果其中一个数组为空，则直接将另一个非空数组赋值给`temp`。最后，根据`(m+n)%2`的值来判断中位数的位置。如果为奇数，则直接取`temp[k]`作为结果；如果为偶数，则取`temp[k]`和`temp[k-1]`的平均值作为结果。

5.实验心得

碰到时间复杂度要求log的，肯定用二分查找；但是双指针算法比普通的归并算法还是要好一些。

代码：

class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {float result;int m=nums1.size();int n=nums2.size();int k=(m+n)/2;vector <int> temp;int i=0,j=0;int count=0;//如两个数组不为空，找到前k+1小数存入新数组if(m>0&& n>0){while(count<=k){if(i==m){temp.push_back(nums2[j++]);count++;continue;}if(j==n){temp.push_back(nums1[i++]);count++;continue;}temp.push_back(nums1[i]<=nums2[j]?nums1[(i++)]:nums2[(j++)]);count++;}}//其中一个数组为空的情况下else if(m==0) temp=nums2;else if(n==0) temp=nums1;//返回中位数if((m+n)%2!=0){result=temp[k];}else {result=(float(temp[k])+float(temp[k-1]))/2;}return result;}    
};

（PS：不是我写的）