题目描述
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
提示：
- nums1.length == m
- nums2.length == n
- 0 <= m <= 1000
- 0 <= n <= 1000
- 1 <= m + n <= 2000
- $-10^6 <= nums1[i], nums2[i] <= 10^6$
解决方法
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
25
26
27
28
29
30
31
32
33
| class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size();
int n = nums2.size();
if (m > n) {
swap(nums1, nums2);
swap(m, n);
}
int left = 0, right = m;
int halfLen = (m + n + 1) / 2;
while (left <= right) {
int partition1 = (left + right) / 2;
int partition2 = halfLen - partition1;
int maxLeft1 = (partition1 == 0) ? INT_MIN : nums1[partition1 - 1];
int minRight1 = (partition1 == m) ? INT_MAX : nums1[partition1];
int maxLeft2 = (partition2 == 0) ? INT_MIN : nums2[partition2 - 1];
int minRight2 = (partition2 == n) ? INT_MAX : nums2[partition2];
if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
if ((m + n) % 2 == 0) {
return (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2.0;
} else {
return max(maxLeft1, maxLeft2);
}
} else if (maxLeft1 > minRight2) {
right = partition1 - 1;
} else {
left = partition1 + 1;
}
}
return 0.0;
}
};
|
结果
执行用时 : 28 ms, 击败 63.85% 使用 C++ 的用户
内存消耗 : 87.49 MB, 击败 90.99% 使用 C++ 的用户
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
if (m > n) {
int[] temp = nums1;
nums1 = nums2;
nums2 = temp;
int tmp = m;
m = n;
n = tmp;
}
int left = 0, right = m, halfLen = (m + n + 1) / 2;
while (left <= right) {
int partition1 = (left + right) / 2;
int partition2 = halfLen - partition1;
int maxLeft1 = (partition1 == 0) ? Integer.MIN_VALUE : nums1[partition1 - 1];
int minRight1 = (partition1 == m) ? Integer.MAX_VALUE : nums1[partition1];
int maxLeft2 = (partition2 == 0) ? Integer.MIN_VALUE : nums2[partition2 - 1];
int minRight2 = (partition2 == n) ? Integer.MAX_VALUE : nums2[partition2];
if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
if ((m + n) % 2 == 0) {
return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2.0;
} else {
return Math.max(maxLeft1, maxLeft2);
}
} else if (maxLeft1 > minRight2) {
right = partition1 - 1;
} else {
left = partition1 + 1;
}
}
return 0.0;
}
}
|
结果
执行用时 : 1 ms, 击败 100.00% 使用 Java 的用户
内存消耗 : 44.79 MB, 击败 5.05% 使用 Java 的用户
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
def find_kth(nums1, start1, nums2, start2, k):
if start1 >= len(nums1):
return nums2[start2 + k - 1]
if start2 >= len(nums2):
return nums1[start1 + k - 1]
if k == 1:
return min(nums1[start1], nums2[start2])
mid_val1 = nums1[start1 + k // 2 - 1] if start1 + k // 2 - 1 < len(nums1) else float('inf')
mid_val2 = nums2[start2 + k // 2 - 1] if start2 + k // 2 - 1 < len(nums2) else float('inf')
if mid_val1 < mid_val2:
return find_kth(nums1, start1 + k // 2, nums2, start2, k - k // 2)
else:
return find_kth(nums1, start1, nums2, start2 + k // 2, k - k // 2)
total_len = len(nums1) + len(nums2)
if total_len % 2 == 1:
return find_kth(nums1, 0, nums2, 0, total_len // 2 + 1)
else:
return (find_kth(nums1, 0, nums2, 0, total_len // 2) + find_kth(nums1, 0, nums2, 0, total_len // 2 + 1)) / 2.0
|
结果
执行用时 : 44 ms, 击败 36.83% 使用 Python 的用户
内存消耗 : 13.29 MB, 击败 18.41% 使用 Python 的用户
Python3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
def find_kth(nums1, start1, nums2, start2, k):
if start1 >= len(nums1):
return nums2[start2 + k - 1]
if start2 >= len(nums2):
return nums1[start1 + k - 1]
if k == 1:
return min(nums1[start1], nums2[start2])
mid_val1 = nums1[start1 + k // 2 - 1] if start1 + k // 2 - 1 < len(nums1) else float('inf')
mid_val2 = nums2[start2 + k // 2 - 1] if start2 + k // 2 - 1 < len(nums2) else float('inf')
if mid_val1 < mid_val2:
return find_kth(nums1, start1 + k // 2, nums2, start2, k - k // 2)
else:
return find_kth(nums1, start1, nums2, start2 + k // 2, k - k // 2)
total_len = len(nums1) + len(nums2)
if total_len % 2 == 1:
return find_kth(nums1, 0, nums2, 0, total_len // 2 + 1)
else:
return (find_kth(nums1, 0, nums2, 0, total_len // 2) + find_kth(nums1, 0, nums2, 0, total_len // 2 + 1)) / 2.0
|
结果
执行用时 : 52 ms, 击败 65.76% 使用 Python3 的用户
内存消耗 : 18.09 MB, 击败 5.00% 使用 Python3 的用户
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
int totalSize = nums1Size + nums2Size;
int *mergedArray = (int *)malloc(sizeof(int) * totalSize);
int i = 0, j = 0, k = 0;
while (i < nums1Size && j < nums2Size) {
if (nums1[i] <= nums2[j]) {
mergedArray[k++] = nums1[i++];
} else {
mergedArray[k++] = nums2[j++];
}
}
while (i < nums1Size) {
mergedArray[k++] = nums1[i++];
}
while (j < nums2Size) {
mergedArray[k++] = nums2[j++];
}
if (totalSize % 2 == 0) {
return (double)(mergedArray[totalSize / 2 - 1] + mergedArray[totalSize / 2]) / 2.0;
} else {
return (double)mergedArray[totalSize / 2];
}
}
|
结果
执行用时 : 12 ms, 击败 83.01% 使用 C 的用户
内存消耗 : 7.38 MB, 击败 15.06% 使用 C 的用户
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
25
26
27
28
29
30
31
32
33
34
35
| public class Solution {
public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.Length;
int n = nums2.Length;
if (m > n) {
int[] temp = nums1;
nums1 = nums2;
nums2 = temp;
int tmp = m;
m = n;
n = tmp;
}
int left = 0, right = m, halfLen = (m + n + 1) / 2;
while (left <= right) {
int partition1 = (left + right) / 2;
int partition2 = halfLen - partition1;
int maxLeft1 = (partition1 == 0) ? int.MinValue : nums1[partition1 - 1];
int minRight1 = (partition1 == m) ? int.MaxValue : nums1[partition1];
int maxLeft2 = (partition2 == 0) ? int.MinValue : nums2[partition2 - 1];
int minRight2 = (partition2 == n) ? int.MaxValue : nums2[partition2];
if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
if ((m + n) % 2 == 0) {
return (Math.Max(maxLeft1, maxLeft2) + Math.Min(minRight1, minRight2)) / 2.0;
} else {
return Math.Max(maxLeft1, maxLeft2);
}
} else if (maxLeft1 > minRight2) {
right = partition1 - 1;
} else {
left = partition1 + 1;
}
}
return 0.0;
}
}
|
结果
执行用时 : 84 ms, 击败 97.55% 使用 C# 的用户
内存消耗 : 53.73 MB, 击败 5.22% 使用 C# 的用户
JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
var findMedianSortedArrays = function(nums1, nums2) {
const mergedArray = [...nums1, ...nums2].sort((a, b) => a - b);
const totalLength = mergedArray.length;
if (totalLength % 2 === 0) {
const midIndex = totalLength / 2;
return (mergedArray[midIndex - 1] + mergedArray[midIndex]) / 2;
} else {
return mergedArray[Math.floor(totalLength / 2)];
}
};
|
结果
执行用时 : 108 ms, 击败 38.49% 使用 JavaScript 的用户
内存消耗 : 54.34 MB, 击败 5.09% 使用 JavaScript 的用户
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| function findMedianSortedArrays(nums1: number[], nums2: number[]): number {
const n = nums1.length + nums2.length;
return (findKth(nums1, nums2, n >> 1) + findKth(nums1, nums2, (n - 1) >> 1)) / 2;
function findKth(nums1: number[], nums2: number[], k: number): number {
if (nums1.length === 0) return nums2[k];
if (nums2.length === 0) return nums1[k];
const i1 = nums1.length >> 1;
const i2 = nums2.length >> 1;
const m1 = nums1[i1];
const m2 = nums2[i2];
if (i1 + i2 < k) {
if (m1 > m2) {
return findKth(nums1, nums2.slice(i2 + 1), k - (i2 + 1));
} else {
return findKth(nums1.slice(i1 + 1), nums2, k - (i1 + 1));
}
} else {
if (m1 > m2) {
return findKth(nums1.slice(0, i1), nums2, k);
} else {
return findKth(nums1, nums2.slice(0, i2), k);
}
}
}
}
|
结果
执行用时 : 88 ms, 击败 95.23% 使用 TypeScript 的用户
内存消耗 : 46.54 MB, 击败 55.23% 使用 TypeScript 的用户
PHP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| class Solution {
function findMedianSortedArrays($nums1, $nums2) {
$m = count($nums1);
$n = count($nums2);
if ($m > $n) {
$temp = $nums1;
$nums1 = $nums2;
$nums2 = $temp;
$temp = $m;
$m = $n;
$n = $temp;
}
$left = 0;
$right = $m;
$halfLen = intval(($m + $n + 1) / 2);
while ($left <= $right) {
$partition1 = intval(($left + $right) / 2);
$partition2 = $halfLen - $partition1;
$maxLeft1 = ($partition1 == 0) ? PHP_INT_MIN : $nums1[$partition1 - 1];
$minRight1 = ($partition1 == $m) ? PHP_INT_MAX : $nums1[$partition1];
$maxLeft2 = ($partition2 == 0) ? PHP_INT_MIN : $nums2[$partition2 - 1];
$minRight2 = ($partition2 == $n) ? PHP_INT_MAX : $nums2[$partition2];
if ($maxLeft1 <= $minRight2 && $maxLeft2 <= $minRight1) {
if (($m + $n) % 2 == 0) {
return (max($maxLeft1, $maxLeft2) + min($minRight1, $minRight2)) / 2.0;
} else {
return max($maxLeft1, $maxLeft2);
}
} elseif ($maxLeft1 > $minRight2) {
$right = $partition1 - 1;
} else {
$left = $partition1 + 1;
}
}
return 0.0;
}
}
|
结果
执行用时 : 20 ms, 击败 96.20% 使用 PHP 的用户
内存消耗 : 19.61 MB, 击败 5.06% 使用 PHP 的用户
Swift
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
func findMedianSortedArrays(_ nums1: [Int], _ nums2: [Int]) -> Double {
var mergeArray = [Int](repeating: 0, count: nums1.count + nums2.count)
var i = 0
var j = 0
var index = 0
while index < mergeArray.count {
if j >= nums2.count || (i < nums1.count && nums1[i] <= nums2[j]) {
mergeArray[index] = nums1[i]
i += 1
} else {
mergeArray[index] = nums2[j]
j += 1
}
index += 1
}
if mergeArray.count % 2 == 0 {
return Double(mergeArray[mergeArray.count / 2 - 1] + mergeArray[mergeArray.count / 2]) / 2.0
} else {
return Double(mergeArray[mergeArray.count / 2])
}
}
}
|
结果
执行用时 : 72 ms, 击败 22.31% 使用 Swift 的用户
内存消耗 : 15.58 MB, 击败 5.79% 使用 Swift 的用户
Kotlin
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
fun findMedianSortedArrays(nums1: IntArray, nums2: IntArray): Double {
val mergeArray = IntArray(nums1.size + nums2.size)
var i = 0
var j = 0
var index = 0
while (index < mergeArray.size) {
if (j >= nums2.size || (i < nums1.size && nums1[i] <= nums2[j])) {
mergeArray[index] = nums1[i]
i++
} else {
mergeArray[index] = nums2[j]
j++
}
index++
}
return if (mergeArray.size % 2 == 0) {
(mergeArray[mergeArray.size / 2 - 1] + mergeArray[mergeArray.size / 2]) / 2.0
} else {
mergeArray[mergeArray.size / 2].toDouble()
}
}
}
|
结果
执行用时 : 268 ms, 击败 63.00% 使用 Kotlin 的用户
内存消耗 : 46.55 MB, 击败 56.00% 使用 Kotlin 的用户
Dart
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 {
double findMedianSortedArrays(List<int> nums1, List<int> nums2) {
int totalLength = nums1.length + nums2.length;
int mid = totalLength ~/ 2;
int i = 0, j = 0;
int prev = 0, current = 0;
while (i + j <= mid) {
prev = current;
if (i < nums1.length && (j >= nums2.length || nums1[i] <= nums2[j])) {
current = nums1[i];
i++;
} else {
current = nums2[j];
j++;
}
}
if (totalLength.isOdd) {
return current.toDouble();
} else {
return (prev + current) / 2.0;
}
}
}
|
结果
执行用时 : 396 ms, 击败 43.75% 使用 Dart 的用户
内存消耗 : 148.22 MB, 击败 87.50% 使用 Dart 的用户
Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
totalLength := len(nums1) + len(nums2)
mid := totalLength / 2
i, j := 0, 0
prev, current := 0, 0
for i+j <= mid {
prev = current
if i < len(nums1) && (j >= len(nums2) || nums1[i] <= nums2[j]) {
current = nums1[i]
i++
} else {
current = nums2[j]
j++
}
}
if totalLength%2 == 1 {
return float64(current)
}
return float64(prev+current) / 2.0
}
|
结果
执行用时 : 8 ms, 击败 90.78% 使用 Go 的用户
内存消耗 : 4.59 MB, 击败 99.81% 使用 Go 的用户
Ruby
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
def find_median_sorted_arrays(nums1, nums2)
total_length = nums1.length + nums2.length
mid = total_length / 2
i = 0
j = 0
prev = 0
current = 0
while i + j <= mid
prev = current
if i < nums1.length && (j >= nums2.length || nums1[i] <= nums2[j])
current = nums1[i]
i += 1
else
current = nums2[j]
j += 1
end
end
if total_length % 2 == 1
return current.to_f
else
return (prev + current) / 2.0
end
end
|
结果
执行用时 : 88 ms, 击败 50.00% 使用 Ruby 的用户
内存消耗 : 208.75 MB, 击败 16.67% 使用 Ruby 的用户
Scala
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| object Solution {
def findMedianSortedArrays(nums1: Array[Int], nums2: Array[Int]): Double = {
val totalLength = nums1.length + nums2.length
val mid = totalLength / 2
var i = 0
var j = 0
var prev = 0
var current = 0
while (i + j <= mid) {
prev = current
if (i < nums1.length && (j >= nums2.length || nums1(i) <= nums2(j))) {
current = nums1(i)
i += 1
} else {
current = nums2(j)
j += 1
}
}
if (totalLength % 2 == 1) {
current.toDouble
} else {
(prev + current) / 2.0
}
}
}
|
结果
执行用时 : 680 ms, 击败 40.00% 使用 Scala 的用户
内存消耗 : 56.56 MB, 击败 100.00% 使用 Scala 的用户
Rust
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| impl Solution {
pub fn find_median_sorted_arrays(nums1: Vec<i32>, nums2: Vec<i32>) -> f64 {
let total_length = nums1.len() + nums2.len();
let mid = total_length / 2;
let mut i = 0;
let mut j = 0;
let mut prev = 0;
let mut current = 0;
while i + j <= mid {
prev = current;
if i < nums1.len() && (j >= nums2.len() || nums1[i] <= nums2[j]) {
current = nums1[i];
i += 1;
} else {
current = nums2[j];
j += 1;
}
}
if total_length % 2 == 1 {
current as f64
} else {
(prev + current) as f64 / 2.0
}
}
}
|
结果
执行用时 : 0 ms, 击败 100.00% 使用 Rust 的用户
内存消耗 : 2.05 MB, 击败 48.63% 使用 Rust 的用户
Racket
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| (define/contract (find-median-sorted-arrays nums1 nums2)
(-> (listof exact-integer?) (listof exact-integer?) flonum?)
(string->number
(real->decimal-string
(find-midian-num-general nums1 nums2)
5))
)
(define (find-midian-num-general nums1 nums2)
(let* ((nums (get-median-list nums1 nums2))
(len (length nums)))
(if (odd? len)
(if (= len 1)
(list-ref nums (- len 1))
(let ((id (/ (- len 1) 2)))
(list-ref nums id)))
(let ((id (/ len 2)))
(/ (+ (list-ref nums (- id 1))
(list-ref nums id))
2)))))
(define (get-median-list nums1 nums2)
(sort (append nums1 nums2) <))
|
结果
执行用时 : 236 ms, 击败 100.00% 使用 Racket 的用户
内存消耗 : 122.28 MB, 击败 100.00% 使用 Racket 的用户
Erlang
1
2
3
4
5
6
7
8
9
| -spec find_median_sorted_arrays(Nums1 :: [integer()], Nums2 :: [integer()]) -> float().
find_median_sorted_arrays(Nums1, Nums2) ->
Merged = lists:sort(Nums1 ++ Nums2),
Length = length(Merged),
Mid = Length div 2,
case Length rem 2 of
0 -> (lists:nth(Mid, Merged) + lists:nth(Mid + 1, Merged)) / 2.0;
_ -> lists:nth(Mid + 1, Merged)
end.
|
结果
执行用时 : 464 ms, 击败 -% 使用 Erlang 的用户
内存消耗 : 61.45 MB, 击败 -% 使用 Erlang 的用户
Elixir
1
2
3
4
5
6
7
8
9
10
11
12
| defmodule Solution do
@spec find_median_sorted_arrays(nums1 :: [integer], nums2 :: [integer]) :: float
def find_median_sorted_arrays(nums1, nums2) do
merged = Enum.sort(nums1 ++ nums2)
length = length(merged)
mid = div(length, 2)
case rem(length, 2) do
0 -> (Enum.at(merged, mid - 1) + Enum.at(merged, mid)) / 2.0
_ -> Enum.at(merged, mid)
end
end
end
|
结果
执行用时 : 520 ms, 击败 -% 使用 Elixir 的用户
内存消耗 : 69.50 MB, 击败 -% 使用 Elixir 的用户