(LeetCode) 4. Median of Two Sorted Arrays

文章目录

  1. 1. Original URL: 4. Median of Two Sorted Arrays
  2. 2. My solutions:
    1. 2.1. With C++:

>

There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Difficulty: Hard
Tags: Binary Search, Array, Divide and Conquer

Original URL: 4. Median of Two Sorted Arrays

My solutions:

With C++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
vector<int> nums = nums2;
nums.insert(nums.begin(), nums1.begin(), nums1.end());
int len = nums.size(), temp;
for(int i=0; i<len; i++)
{
for(int j=i+1; j<len; j++)
{
if(nums[j] < nums[i])
{
temp = nums[j];
nums[j] = nums[i];
nums[i] = temp;
}
}
}
if(len % 2 == 0)
{return (nums[len/2] + nums[len/2-1]) / 2.0;}
else
{return nums[len/2];}
}
};

NOTE(2016/6/2):
My solution is based on the Bubble Sort.This solution’s overall run time complexity is O(n^2),and I can not come up with a O(log (m+n)) solution yet.

See my 30+ solutions of LeetCode on GitHub