一、使用额外空间,类似归并排序的做法
class Solution { public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int m = nums1.size();int n = nums2.size(); int temp[(m+n)/2+1]; //不需要用到(m+n)大小的数组,最多放一半多一点就能够确定结果 //接下来的程序和归并排序中,两个有序数组合并特别像,不同之处在于这个只需要存到(m+n)/2+1 int count = 0,i = 0,j = 0; while(i < m && j < n && count <= (m+n)/2){ if(nums1[i] < nums2[j]){ temp[count++] = nums1[i++]; } else{ temp[count++] = nums2[j++]; } } while(i < m && count <= (m+n)/2) temp[count++] = nums1[i++]; while(j < n && count <= (m+n)/2) temp[count++] = nums2[j++]; if((m+n)%2==0) return (temp[(m+n)/2-1]*1.0+temp[(m+n)/2]*1.0)/2.0; else return temp[(m+n)/2]*1.0; /*//这是原本尝试不使用额外空间的代码,特别丑陋 int m = nums1.size();int n = nums2.size(); int count = 0,i = 0,j = 0; while(i < m && j < n && count < (m+n)/2){ if(nums1[i] < nums2[j]) j++; else i++; count++; } if(count == (m+n)/2){ if((m+n)%2==0){ if(i == m){ int a = max(nums1[i-1],nums2[j]); int b = nums2[j+1]; return (a*1.0+b*1.0)/2.0; } if(j == n){ int a = max(nums1[i],nums2[j-1]); int b = nums2[i+1]; return (a*1.0+b*1.0)/2.0; } return (nums1[i]*1.0+nums2[j]*1.0)/2.0; } else{ if(nums1[i] < nums2[j]) j++; else i++; return max(nums1[i],nums2[j])*1.0; } } if(i < m){ if((m+n)%2==0){ while(count < (m+n)/2) i++; return (nums1[i]*1.0+nums1[i+1]*1.0)/2.0; } else{ while(count < (m+n)/2) i++; return nums1[i+1]*1.0; } } if(j < m){ if((m+n)%2==0){ while(count < (m+n)/2) j++; return (nums2[j]*1.0+nums2[j+1]*1.0)/2.0; } else{ while(count < (m+n)/2) j++; return nums2[j+1]*1.0; } } return 0; */ } };
二、枚举,利用单调数组的性质
标签:正序,数组,int,中位数,&&,leetcode From: https://www.cnblogs.com/uacs2024/p/18542206