Array-Hard
Abstract：leetcode 线性表 hard 难度题解合集
4. Median of Two Sorted Arrays
解法一：直接排序
直接拼起来，再排序，复杂度同排序复杂度
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
for(int i : nums2) nums1.push_back(i);
std::sort(nums1.begin(), nums1.end());
int len = nums1.size();
if(len % 2 != 0)
return (double)nums1[len/2];
else
return (((double)nums1[(len/2) - 1] + (double)nums1[len/2]) / 2);
}
};
解法二：插入排序
解法一是O((m + n)log(m + n))，显然如果插入排序的话，时间复杂度至少可以是O(m+n)
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int i = 0, j = 0;
vector<int> nums;
while(i < nums1.size() || j < nums2.size()){
if(i >= nums1.size())
nums.push_back(nums2[j++]);
else if(j >= nums2.size())
nums.push_back(nums1[i++]);
else if(nums1[i] < nums2[j])
nums.push_back(nums1[i++]);
else
nums.push_back(nums2[j++]);
}
int len = nums.size();
if(len % 2 != 0)
return (double)nums[len/2];
else
return (((double)nums[(len/2) - 1] + (double)nums[len/2]) / 2);
}
};