[leetcode] 4. Median of Two Sorted Arrays解題報告
タイトルリンク:https://leetcode.com/problems/median-of-two-sorted-arrays/
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)).
考え方:これも古典的な問題で、その原理はやはり1つの配列が中位数を求める二分探索と似ている.
leetcodeの前の同級生の注意に感謝して、私のアルゴリズムに問題があることを発見して、時間の複雑さはlinearで対数の時間ではありませんて、そこで再び私のコードを見て、とても問題があって、今再び1つ書きました.
2つの配列があり、その長さが奇数である場合、中位数は1つの数であり、長さと偶数である場合、中位数は2つの数の平均値である.
1つの配列の長さが0の場合、中位数は簡単に得られます.そうしないと、次の状況を考慮します.
配列1の長さを最小に保つには、検索するたびに取得する2つの配列の位置を2つの候補位置、すなわちその位置とkに保つ必要があります.
1.nums 1[k 1]k 1の位置のサブ配列を再帰的に検索する
2.nums 1[k 1]>nums 2[k 2]の場合、中位数はnums 2の<=k 2の位置にないことを示すので、nums 2の>k 2の位置のサブ配列を再帰的に検索する
3.nums 1[k 1]=nums 2[k 2]の場合、k番目の数が見つかり、
コードは次のとおりです.
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)).
考え方:これも古典的な問題で、その原理はやはり1つの配列が中位数を求める二分探索と似ている.
leetcodeの前の同級生の注意に感謝して、私のアルゴリズムに問題があることを発見して、時間の複雑さはlinearで対数の時間ではありませんて、そこで再び私のコードを見て、とても問題があって、今再び1つ書きました.
2つの配列があり、その長さが奇数である場合、中位数は1つの数であり、長さと偶数である場合、中位数は2つの数の平均値である.
1つの配列の長さが0の場合、中位数は簡単に得られます.そうしないと、次の状況を考慮します.
配列1の長さを最小に保つには、検索するたびに取得する2つの配列の位置を2つの候補位置、すなわちその位置とkに保つ必要があります.
1.nums 1[k 1]
2.nums 1[k 1]>nums 2[k 2]の場合、中位数はnums 2の<=k 2の位置にないことを示すので、nums 2の>k 2の位置のサブ配列を再帰的に検索する
3.nums 1[k 1]=nums 2[k 2]の場合、k番目の数が見つかり、
コードは次のとおりです.
class Solution {
public:
double findK(vector<int>& nums1, vector<int>& nums2, int k)
{
int len1=nums1.size(), len2=nums2.size();
if(len1 > len2) return findK(nums2, nums1, k);
if(len1 == 0) return nums2[k-1];
if(k == 1) return min(nums1[0], nums2[0]);
int k1 = min(k/2, len1), k2 = k - k1;
if(nums1[k1-1] < nums2[k2-1])
{
vector<int> tem(nums1.begin()+k1, nums1.end());
return findK(tem, nums2, k-k1);
}
if(nums1[k1-1] > nums2[k2-1])
{
vector<int> tem(nums2.begin()+k2, nums2.end());
return findK(nums1, tem , k-k2);
}
return nums1[k1-1];
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int len1=nums1.size(), len2=nums2.size();
int val = findK(nums1, nums2, (len1+len2+1)/2);
if((len1+len2)%2) return val;
return (val + findK(nums1, nums2, (len1+len2)/2+1))/2.0;
}
};