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)).
You may assume nums1 and nums2 cannot be both empty.
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
// 44ms
class Solution {
/**
* @param Integer[] $nums1
* @param Integer[] $nums2
* @return Float
*/
function findMedianSortedArrays($nums1, $nums2) {
$num = array_merge($nums1, $nums2);
sort($num);
$len = count($num);
if($len%2 !== 0){
$index = floor($len/2);
return $num[$index];
} else {
$index= $len/2;
return ($num[$index-1]+$num[$index])/2;
}
}
}
// 44ms
class Solution {
/**
* @param Integer[] $nums1
* @param Integer[] $nums2
* @return Float
*/
function findMedianSortedArrays($nums1, $nums2) {
if (empty($nums1) && empty($nums2)) {
return (float)0;
}
$nums = array_merge($nums1, $nums2);
sort($nums);
if (count($nums) % 2 !=0) {
return $nums[count($nums) / 2 ];
}else{
return ($nums[count($nums) / 2 ]+ $nums[count($nums) / 2 -1]) / 2;
}
}
}
//24ms
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
var c []int
c = append(nums1, nums2...)
sort.Ints(c)
l := len(c)
if l%2 == 0 {
mid := l/2
return (float64(c[mid])+float64(c[mid-1]))/2
} else {
return float64(c[l/2])
}
}
//16MS 好像不可以用内置排序函数呀。。。。
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
m := len(nums1)
n := len(nums2)
if (m + n) & 1 == 1 {
return float64(findKthSmallNumInSortedArray(nums1, nums2, (m+n)/2 + 1))
}
return float64(findKthSmallNumInSortedArray(nums1, nums2, (m+n)/2) + findKthSmallNumInSortedArray(nums1, nums2, (m+n)/2 + 1)) / 2
}
func minInt(a, b int) int {
if a < b {
return a
}
return b
}
func findKthSmallNumInSortedArray(nums1, nums2 []int, k int) int {
len1 := len(nums1)
len2 := len(nums2)
base1 := 0
base2 := 0
for {
if len1 == 0 {
return nums2[base2 + k - 1]
}
if len2 == 0 {
return nums1[base1 + k - 1]
}
if k == 1 {
return minInt(nums1[base1], nums2[base2])
}
i := minInt(k / 2, len1)
j := minInt(k - i, len2)
a := nums1[base1 + i - 1]
b := nums2[base2 + j - 1]
if i + j == k && a == b {
return a
}
if a <= b {
base1 = base1 + i
len1 = len1 - i
k = k - i
}
if a >= b {
base2 = base2 + j
len2 = len2 - j
k = k - j
}
}
}
方法一一般是自己实现的方法，其他方式是在discuss中查找的更为优秀的方法，用作学习和借鉴。