4. Median of Two Sorted Arrays
1.問題
找出兩list合併後的中位數

2.想法
O(m + n): 比較兩list的元素並將最小值先放入list中, return list的中位數
O(Log(m + n)):
k的初始值為(m + n) / 2, 每次都將k折半, 並比較nums1[k/2]與nums2[k/2], 如果nums1[k/2]較大, 則下次迭代時將不把比nums2[k/2]小的數字納入比較; 反之亦然
此做法等於每次屑減 (m + n) /2, 再將剩下的(m + n) / 2個數字進行下一次迭代, 等同於使用Binary search
3.程式碼
O(m + n)
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int size1 = nums1.size();
int size2 = nums2.size();
int index1 = 0, index2 = 0;
vector<int> v;
while (index1 < size1 && index2 < size2)
{
if (nums1[index1] < nums2[index2])
{
v.push_back(nums1[index1]);
index1++;
}
else if (nums1[index1] > nums2[index2])
{
v.push_back(nums2[index2]);
index2++;
}
else
{
v.push_back(nums1[index1]);
v.push_back(nums2[index2]);
index1++;
index2++;
}
}
while (index1 < size1)
{
v.push_back(nums1[index1]);
index1++;
}
while (index2 < size2)
{
v.push_back(nums2[index2]);
index2++;
}
return ((size1 + size2) % 2 == 0) ? (double)(v[(size1 + size2 - 1)/2] + v[(size1 + size2 - 1)/2 + 1])/2 : v[(size1 + size2)/2];
}
}
O(Log(m + n))
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int total = nums1.size() + nums2.size();
if (total & 0x1)
{
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;
}
private:
double findKth(vector<int>& a, int idx1, vector<int>& b, int idx2, int k)
{
int m = a.size() - idx1;
int n = b.size() - idx2;
if (m > n) {
return findKth(b, idx2, a, idx1, k);
}
if (m == 0) {
return b[k - 1];
}
if (k == 1) {
return min(a[idx1], b[idx2]);
}
//divide k into two parts
int pa = min(k / 2, m), pb = k - pa;
if (a[idx1 + pa - 1] < b[idx2 + pb - 1]) {
return findKth(a, idx1 + pa, b, idx2, k - pa);
}
else if (a[idx1 + pa - 1] > b[idx2 + pb - 1]) {
return findKth(a, idx1, b, idx2 + pb, k - pb);
}
else {
return a[pa - 1];
}
}
};
4.References
Last updated