c++:
因为数组有序，则无需排序，维护两个指针，依次移动，时间复杂度O(m + n)，同一个程序，有时候显示16ms，有时候44ms,离谱
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
// 因为数组有序，则无需排序，维护两个指针，依次移动，时间复杂度O(m + n)
int point1 = 0;
int point2 = 0;
int n1 = nums1.size();
int n2 = nums2.size();
int mid = 0;
int temp = 0;
int flag = 0; // 1为偶，奇为0
int temp_pre = -1;
if((n1 + n2) % 2 == 0){
flag = 1;
mid = (n1 + n2) / 2;
} else{
flag = 0;
mid = ((n1 + n2 + 1) / 2) - 1;
}
for (int i = 0; i <= mid; ++i){
if(i != mid - 1 || flag == 0){
if(point1 < n1 && point2 < n2){
if(nums1[point1] < nums2[point2]){
temp = nums1[point1];
point1++;
}else{
temp = nums2[point2];
point2++;
}
}
else if(point1 < n1 && point2 >= n2) // n1 没到底，n2到底
{
temp = nums1[point1];
point1++;
}
else if(point1 >= n1 && point2 < n2) // n1 没到底，n2到底
{
temp = nums2[point2];
point2++;
}
}
else if(flag == 1 && i == mid -1){
if(point1 < n1 && point2 < n2){
if(nums1[point1] < nums2[point2]){
temp = nums1[point1];
temp_pre = temp;
point1++;
}else{
temp = nums2[point2];
temp_pre = temp;
point2++;
}
}
else if(point1 < n1 && point2 >= n2) // n1 没到底，n2到底
{
temp = nums1[point1];
temp_pre = temp;
point1++;
}
else if(point1 >= n1 && point2 < n2) // n1 没到底，n2到底
{
temp = nums2[point2];
temp_pre = temp;
point2++;
}
}
}
// double ans = temp;
double ans = 0.00000;
cout<< temp<<"\n";
cout<< temp_pre<<"\n";
if(flag == 1){
ans = (temp + temp_pre) / 2.0;
}
else{
ans = temp;
}
cout<< ans;
return ans;
}
};
python:
暴力排序都能过，我服了
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
nums1.extend(nums2)
nums1.sort()
n=len(nums1)
if n==0:
return 0
if n==1:
return nums1[0]
if n%2==1:
return nums1[(n+1)//2-1]
if len(nums1)%2==0:
return nums1[n//2-1]/2 +nums1[n//2]/2
