標(biāo)簽（空格分隔）： C++ 算法 LetCode 數(shù)組
每日算法——letcode系列
問(wèn)題 Median of Two Sorted Arrays
Difficulty: Hard
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)).
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
}
};
翻譯
兩個(gè)有序數(shù)組的中位數(shù)
難度系數(shù)：困難
有兩個(gè)大小分別為m和n的 nums1和nums2有序數(shù)組茂翔。 找出這兩個(gè)有序數(shù)組的中位數(shù)芹缔。 時(shí)間復(fù)雜度應(yīng)為$O(log (m+n))$.
思路
先轉(zhuǎn)化成topK問(wèn)題稻轨，再分兩種情況：
- m + n為奇數(shù)時(shí)，返回第K就好
- m + n為偶數(shù)時(shí)蛋勺，返回第K和K + 1的平均值
由于題目要求是O(log(m+n))時(shí)間復(fù)雜度逮壁，那必須得用有序的信息，想到二分法付枫，總想把兩數(shù)組各減一半最好，但這種可能把中位數(shù)也剔除了驰怎，
如：
[1, 2, 5, 6] -> [5, 6]
[3, 4, 7, 8] -> [7, 8] 這樣就把中位數(shù)4給剔除了阐滩，但可以得用一點(diǎn)，上面?zhèn)€數(shù)組中的[1, 2]是可以剔除的县忌。
兩長(zhǎng)度分別為m, n的數(shù)組A, B掂榔，假設(shè)k = $\frac{（m + n) }{2}$ 继效。
將k分成兩成pa,pb兩部分，由于是兩個(gè)數(shù)組装获，長(zhǎng)度不一致瑞信，為不越界，有兩種分法：（假設(shè)m>n）
- 當(dāng)$\frac{k}{2}$ $\leq$n時(shí)穴豫， 直接分成pa = pa = $\frac{k}{2}$
- 當(dāng)$\frac{k}{2}$ > n時(shí), pa = n, pb = k - pa
下面分析當(dāng)$\frac{k}{2}$ $\leq$n的三種情況
- A[$\frac{k}{2}$] == B[$\frac{k}{2}$]
- A[$\frac{k}{2}$] > B[$\frac{k}{2}$]
- A[$\frac{k}{2}$] < B[$\frac{k}{2}$]
第一種情況：
如果將B合并到A凡简，那么B[0]到B[$\frac{k}{2}$-1]肯定在A的左邊， B[$\frac{k}{2}$+1]到B[n]肯定放在A的右邊精肃，那中位數(shù)即為A[$\frac{k}{2}$]秤涩、B[$\frac{k}{2}$]第二種情況：
如果：中位數(shù)在B[0]到B[$\frac{k}{2}$]中， 假設(shè)中位數(shù)的索引為mid肋杖。
那么B[0] $\leq$B[mid] $\leq$B[$\frac{k}{2}$]溉仑， 則B中至少有n - $\frac{k}{2}$個(gè)在B[mid] 右邊
由于A[$\frac{k}{2}$] > B[$\frac{k}{2}$]挖函， 則A中至少有m - $\frac{k}{2}$ + 1個(gè)在B[mid] 右邊
則至少有n - $\frac{k}{2}$ + m - $\frac{k}{2}$ + 1 = k + 1個(gè)數(shù)在B[mid]的右邊, 則當(dāng)且僅當(dāng)mid = $\frac{k}{2}$滿足要求状植， 比如A = [6], B = [1, 2, 8]，如果A[$\frac{k}{2}$ -1] > B[$\frac{k}{2}$ -1]呢怨喘？
同上分析得：則至少有n - （$\frac{k}{2}$ -1) + m - ($\frac{k}{2}$-1) + 1 = k + 3> k+1個(gè)數(shù)在B[mid]的右邊, 則中位數(shù)肯定不在B[0]到B[$\frac{k}{2}$ -1]中津畸，可剔除第三種情況同第二種類似：當(dāng)A[$\frac{k}{2}$ -1] < B[$\frac{k}{2}$ -1]中位數(shù)肯定不在A[0]到A[$\frac{k}{2}$ -1]中。
由上分析可得：
- A[$\frac{k}{2}$-1] == B[$\frac{k}{2}$-1時(shí)：A[$\frac{k}{2}$-1]必怜、 B[$\frac{k}{2}$-1]為中位數(shù)
- A[$\frac{k}{2}$-1] > B[$\frac{k}{2}$-1]時(shí)：中位數(shù)肯定不在B[0]到B[$\frac{k}{2}$-1]中
- A[$\frac{k}{2}$-1] < B[$\frac{k}{2}$-1]時(shí)：中位數(shù)肯定不在A[0]到A[$\frac{k}{2}$-1]中
則我們可以遞歸的剔除二個(gè)數(shù)組中的一些數(shù)
中止條件：
- 當(dāng)A[$\frac{k}{2}$-1] == B[$\frac{k}{2}$-1時(shí)肉拓，返回其中一個(gè)
- 當(dāng)A、B中一個(gè)為空時(shí)梳庆， 分別返回B[k-1]或A[k-1]
- 當(dāng)k = 1時(shí)暖途， 返回A[0]、B[0]中小的一個(gè)
當(dāng)$\frac{k}{2}$ > n時(shí), 也是同樣的分析方法
代碼
//
// main.cpp
// Median of Two Sorted Arrays
//
// Created by zhz on 15/12/15.
// Copyright (c) 2015年 zhz. All rights reserved.
//
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = static_cast<int>(nums1.size());
int n = static_cast<int>(nums2.size());
int k = (m + n + 1) / 2;
if ((m + n) % 2 != 0){
return findKthBigNum(nums1, nums2, k);
}
else{
return (findKthBigNum(nums1, nums2, k + 1) + findKthBigNum(nums1, nums2, k)) / 2.0;
}
}
private:
double findKthBigNum(vector<int>& nums1, vector<int>& nums2, int k){
int m = static_cast<int>(nums1.size());
int n = static_cast<int>(nums2.size());
if (n > m){
return findKthBigNum(nums2, nums1, k);
}
if (n == 0){
return nums1[k - 1];
}
if (k == 1){
return nums1[0] < nums2[0] ? nums1[0] : nums2[0];
}
int pa = min(k / 2, n), pb = k - pa;
if (nums1[pb - 1] == nums2[pa - 1]){
return nums2[pa - 1];
}
else if (nums1[pb - 1] > nums2[pa - 1])
{
vector<int> tempNums;
if (pa <= nums2.size()){
tempNums.assign(nums2.begin() + pa, nums2.end());
k = k - pa;
}
else{
k = k - static_cast<int>(nums2.size());
}
return findKthBigNum(nums1, tempNums, k);
}
else
{
vector<int> tempNums;
if (pb <= nums1.size()){
tempNums.assign(nums1.begin() + pb, nums1.end());
k = k - pb;
}
else{
k = k - static_cast<int>(nums1.size());
}
return findKthBigNum(tempNums, nums2, k);
}
}
};
int main(int argc, const char * argv[]) {
vector<int> nums1 = {3};
vector<int> nums2 = {1, 2, 4};
auto s = new Solution();
double mid = s->findMedianSortedArrays(nums1, nums2);
std::cout << "Hello, World!\n";
return 0;
}
后記： 代碼的實(shí)現(xiàn)有很多細(xì)節(jié)活膏执，一定要多練驻售，不能光靠想
還有些細(xì)節(jié)沒(méi)完善，比如求平均值最好用位操作更米，不會(huì)越界
