leetcode 04 Median of Two Sorted Arrays
7390 ワード
この問題では,2つの秩序配列の中位数を求め,時間的複雑度をO(log(m+n))に制限し,この時間的複雑度を見ると,二分ルックアップ法を用いて解くべきであることが自然に考えられる.しかし、この問題がHardと定義されているのも理由があり、2つの未結合の秩序配列の間で二分法を使用するのは難しい.ここではK番目の要素を見つけるために関数を定義する必要がある.2つの配列の長さの和のパリティが不確定であるため、状況を分けて議論する必要がある.奇数の場合、最も中間の数を直接見つければよい.偶数の場合は真ん中の2つの数の平均値が必要です.次に、K番目の要素を見つける方法を重点的に見てみましょう.まず、配列1の長さを配列2の長さ以下にする必要があります.では、配列1の長さが配列2の長さより大きい場合は、2つの配列を交換すればいいと判断し、小さな配列が空であるかどうかを判断し、空であれば、別の配列でK番目を探すだけです.もう1つのケースは,K=1の場合,2つの配列の最初の要素を比較し,より小さいものを返すだけで,最初の要素を探すことを示す.
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int total = nums1.size() + nums2.size();
if (total % 2 == 1) {
return findKth(nums1, 0, nums2, 0, total / 2 + 1);
} else {
return (findKth(nums1, 0, nums2, 0, total / 2) + findKth(nums1, 0, nums2, 0, total / 2 + 1)) / 2;
}
}
double findKth(vector<int> &nums1, int i, vector<int> &nums2, int j, int k) {
if (nums1.size() - i > nums2.size() - j) return findKth(nums2, j, nums1, i, k);
if (nums1.size() == i) return nums2[j + k - 1];
if (k == 1) return min(nums1[i], nums2[j]);
int pa = min(i + k / 2, int(nums1.size())), pb = j + k - pa + i;
if (nums1[pa - 1] < nums2[pb - 1])
return findKth(nums1, pa, nums2, j, k - pa + i);
else if (nums1[pa - 1] > nums2[pb - 1])
return findKth(nums1, i, nums2, pb, k - pb + j);
else
return nums1[pa - 1];
}
}; ， ， findKth ， ， 。
class Solution {
public:
double findMedianSortedArrays(vector& nums1, vector& nums2) {
int m = nums1.size(), n = nums2.size();
return (findKth(nums1, nums2, (m + n + 1) / 2) + findKth(nums1, nums2, (m + n + 2) / 2)) / 2.0;
}
int findKth(vector nums1, vector nums2, int k) {
int m = nums1.size(), n = nums2.size();
if (m > n) return findKth(nums2, nums1, k);
if (m == 0) return nums2[k - 1];
if (k == 1) return min(nums1[0], nums2[0]);
int i = min(m, k / 2), j = min(n, k / 2);
if (nums1[i - 1] > nums2[j - 1]) {
return findKth(nums1, vector(nums2.begin() + j, nums2.end()), k - j);
} else {
return findKth(vector(nums1.begin() + i, nums1.end()), nums2, k - i);
}
return 0;
}
};