LeetCode https://leetcode.cn/problems/median-of-two-sorted-arrays/
题目描述
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
思路
归并排序中的合并算法, 题目也可以理解为找到第K(m+n+1)/2小的数, 所以实际不用完全合并
代码
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
43
44
| class Solution {
public:
double findMedianSortedArrays(std::vector<int>& nums1, std::vector<int>& nums2) {
std::vector<int> tmp;
int count = 0, tmp1 = 0, tmp2 = 0, left = 0, righ = 0;
int size1 = nums1.size();
int size2 = nums2.size();
int total = size1 + size2;
while (left < size1 || righ < size2) {
if (left < size1 && righ < size2) {
const int & v1 = nums1[left];
const int & v2 = nums2[righ];
if (v1 < v2) {
tmp1 = tmp2;
tmp2 = v1;
++count;
++left;
} else {
tmp1 = tmp2;
tmp2 = v2;
++count;
++righ;
}
} else if (left < size1) {
tmp1 = tmp2;
tmp2 = nums1[left];
++count;
++left;
} else if (righ < size2) {
tmp1 = tmp2;
tmp2 = nums2[righ];
++count;
++righ;
}
if (count >= (total / 2) + 1)
break;
}
if (total % 2 == 0) {
return (tmp1 + tmp2) / 2.0;
} else {
return tmp2;
}
}
};
|
