4.尋找兩個正序數組的中位數

一、問題描述

給定兩個大小分別為?m?和?n?的正序（從小到大）數組?nums1?和?nums2。請你找出并返回這兩個正序數組的?中位數?。

二、問題簡化

?所謂中位數，就是指一個數組中間位置的數字。當元素數量為奇數時，就是最中間的那個數字；而當元素數量為偶數時，為中間兩個數字的平均值（求和除以2）。

這里用數列表示并不恰當，數列的定義是正整數集。所以仍舊以模板T抽象表示元素類型，不過對于抽象的類型T來說，我們要求中位數就必須使用求和操作和除以2的操作，再考慮到整型除以2會發生截斷操作，干脆就只返回數字即可：

//返回值類型，0個元素代表原數組均為空，1個元素代表奇數，2個元素代表偶數 vector<T>

這里的問題實際并沒有描述清楚，中位數本質是在一個數組中尋找，而題目的意思是合并數組后再尋找。所以也不一定是只合并兩個數組，所以傳入數組的參數如下：

list<vector<T>*>

所以函數接口為：

template<typename T> vector<T> findMedian(list<vector<T>*>);?

三、功能實現

最容易想到的辦法是按序合并所有數組后，再判斷奇偶返回對應的值。

而合并數組不僅會占據所有數組大小的空間，并且還涉及到元素的拷貝，這樣就太慢了！這個區別不是數量級的區別，而是做一千個俯臥撐和動一千下手指的區別。

1.求出合并后的數組總長度M（整型），很明顯我們并不需要真的合并，總長度就是各個數組長度之和。

2.如果M為奇數，則中位數為M/2位置的數；如果M為偶數，則中位數為M/2 - 1和M/2位置的數的平均值。（整型除法，直接截斷）

3.如何遍歷到指定位置的數？每個數組記錄下一個值，為當前位置。每次遍歷從數組當前位置選擇最小值的那個，然后選中的那個數組當前位置增加1。（這實際是一個可抽象的問題，從N個有序數組中，返回合并后的數組，指定位置的元素）

所以我先實現了從N個有序數組中尋找指定位置的元素這個功能：

//從N個有序數組中尋找 指定位置的元素 //所有參數均為升序 template<typename T> vector<T> FindSortedArrays(const vector<vector<T>*>& all_vec, const vector<int>& vec_target, int m = -1) {//沒有數組，返回錯誤if (all_vec.empty()|| vec_target.empty())return vector<T>();//總長度if (m == -1){m = 0;for (auto& iter : all_vec){m += iter->size();}}//總長度錯誤if (m <= 0)return vector<T>();int all_vec_size = all_vec.size();//每個數組設置一個位置標記vector<int> arr_pos(all_vec_size, 0);//目標位置 當前int i_target = 0;vector<T> ret;for (int i = 0; i != m; ++i){//從所有數組的當前位置返回最小值bool b_inited_min = false;T v_min;int j_min;//最小值所在的jfor (int j = 0; j != all_vec_size; ++j){vector<T>& vec_ref = *all_vec[j];int cur_pos = arr_pos[j];//越界跳過if (cur_pos >= vec_ref.size())continue;//最小值未初始化if (!b_inited_min){b_inited_min = true;v_min = vec_ref[cur_pos];j_min = j;}else{//已有最小值，則比較覆蓋if (vec_ref[cur_pos] < v_min){v_min = vec_ref[cur_pos];j_min = j;}}}//斷言：未找到最小值if (!b_inited_min){return vector<T>();}//最小數組當前位置加1++arr_pos[j_min];if (i == vec_target[i_target]){ret.push_back(v_min);if (++i_target >= vec_target.size())return ret;}}return ret; }

測試結果如下：

我一共輸入了4個數組，并且通過FindSortedArrays函數直接返回了合并之后的指定位置值（函數內部沒有實際的合并操作，這個函數叫GetSortedArrays應該更合適）。

然后尋找中位數就變得很簡單，通過&1判斷奇偶即可，奇數返回m/2位置的值，偶數返回m/2 - 1 ,m/2的平均值：

//尋找中位數 template<typename T> vector<T> FindMedian(const vector<vector<T>*>& all_vec) {//沒有數組，返回錯誤if (all_vec.empty())return vector<T>();//計算總長度int m = 0;for (auto& iter : all_vec){m += iter->size();}//奇數if (m & 1){return FindSortedArrays(all_vec, { m / 2 }, m);}else{return FindSortedArrays(all_vec, { m / 2 - 1, m / 2 }, m);} }

四、測試結果

我再復制幾組數據用于測試：

?

網上代碼的一般思路是實際合并了數組再直接返回對應位置的值，而這個合并操作就占據了大量的空間和時間，而我的代碼的優勢在于不必占據大量的臨時空間，還可以減少合并時的拷貝操作。但是仍然需要比較很多次和拷貝一定次數。

等有空了我再補充測試一下它們之間到底誰更快。不過我在LeetCode里面有測試，經過我反復嘗試很明顯編譯器沒有做優化，而且輸入數據量也很低，它的速度沒什么參考價值。

完整代碼如下：

#include <iostream> #include <vector> #include <list> #include <algorithm> using namespace std;//從N個有序數組中尋找 指定位置的元素 //所有參數均為升序 template<typename T> vector<T> FindSortedArrays(const vector<vector<T>*>& all_vec, const vector<int>& vec_target, int m = -1) {//沒有數組，返回錯誤if (all_vec.empty()|| vec_target.empty())return vector<T>();//總長度if (m == -1){m = 0;for (auto& iter : all_vec){m += iter->size();}}//總長度錯誤if (m <= 0)return vector<T>();int all_vec_size = all_vec.size();//每個數組設置一個位置標記vector<int> arr_pos(all_vec_size, 0);//目標位置 當前int i_target = 0;vector<T> ret;for (int i = 0; i != m; ++i){//從所有數組的當前位置返回最小值bool b_inited_min = false;T v_min;int j_min;//最小值所在的jfor (int j = 0; j != all_vec_size; ++j){vector<T>& vec_ref = *all_vec[j];int cur_pos = arr_pos[j];//越界跳過if (cur_pos >= vec_ref.size())continue;//最小值未初始化if (!b_inited_min){b_inited_min = true;v_min = vec_ref[cur_pos];j_min = j;}else{//已有最小值，則比較覆蓋if (vec_ref[cur_pos] < v_min){v_min = vec_ref[cur_pos];j_min = j;}}}//斷言：未找到最小值if (!b_inited_min){return vector<T>();}//最小數組當前位置加1++arr_pos[j_min];if (i == vec_target[i_target]){ret.push_back(v_min);if (++i_target >= vec_target.size())return ret;}}return ret; }//尋找中位數 template<typename T> vector<T> FindMedian(const vector<vector<T>*>& all_vec) {//沒有數組，返回錯誤if (all_vec.empty())return vector<T>();//計算總長度int m = 0;for (auto& iter : all_vec){m += iter->size();}//奇數if (m & 1){return FindSortedArrays(all_vec, { m / 2 }, m);}else{return FindSortedArrays(all_vec, { m / 2 - 1, m / 2 }, m);} }int main() {{cout << "-----------------------------------All arrays------------------------------" << endl;vector<int> vecs[] = {{1,2,5,11,14,99,105},{3,6,8,9,12,13},{2,107,113,120,999},{-1, 117}};//合并并排序vector<int> vecs_add;for (auto& iter : vecs){//打印for (auto& iter1 : iter){cout << iter1 << " ";}cout << endl;vecs_add.insert(vecs_add.end(), iter.begin(), iter.end());}sort(vecs_add.begin(), vecs_add.end());//打印合并之后cout << "-----------------------------------After the merger is------------------------------" << endl;for (auto& iter1 : vecs_add){cout << iter1 << " ";}cout << endl;//vector<vector<int>*> vec_temp;for (auto& iter : vecs)vec_temp.push_back(&iter);vector<int> vec_find = { 0,5,10,12 };//要尋找的位置auto ret0 = FindSortedArrays(vec_temp, vec_find);//打印查找結果cout << "-----------------------------------Find results------------------------------" << endl;for (int i = 0; i != ret0.size(); ++i){cout << "index " << vec_find[i] << " is " << ret0[i] << endl;}//auto ret1 = FindMedian(vec_temp);//打印中位數cout << "-----------------------------------Median is------------------------------" << endl;if (ret1.size() == 1){cout << ret1[0] << endl;}else if (ret1.size() == 2){//轉為小數cout << float(ret1[0] + ret1[1]) * 0.5f << endl;}else{cout << "error" << endl;}}cout << "================================================================================" << endl;{cout << "-----------------------------------All arrays------------------------------" << endl;vector<int> vecs[] = {{5,6,7}};//合并并排序vector<int> vecs_add;for (auto& iter : vecs){//打印for (auto& iter1 : iter){cout << iter1 << " ";}cout << endl;vecs_add.insert(vecs_add.end(), iter.begin(), iter.end());}sort(vecs_add.begin(), vecs_add.end());//打印合并之后cout << "-----------------------------------After the merger is------------------------------" << endl;for (auto& iter1 : vecs_add){cout << iter1 << " ";}cout << endl;//vector<vector<int>*> vec_temp;for (auto& iter : vecs)vec_temp.push_back(&iter);vector<int> vec_find = { 1, 3 };//要尋找的位置auto ret0 = FindSortedArrays(vec_temp, vec_find);//打印查找結果cout << "-----------------------------------Find results------------------------------" << endl;for (int i = 0; i != ret0.size(); ++i){cout << "index " << vec_find[i] << " is " << ret0[i] << endl;}//auto ret1 = FindMedian(vec_temp);//打印中位數cout << "-----------------------------------Median is------------------------------" << endl;if (ret1.size() == 1){cout << ret1[0] << endl;}else if (ret1.size() == 2){//轉為小數cout << float(ret1[0] + ret1[1]) * 0.5f << endl;}else{cout << "error" << endl;}}cout << "================================================================================" << endl;{cout << "-----------------------------------All arrays------------------------------" << endl;vector<int> vecs[] = {{5,6,7},{1,1,1,1,2,2,2,5,6,7},{9,11,100}};//合并并排序vector<int> vecs_add;for (auto& iter : vecs){//打印for (auto& iter1 : iter){cout << iter1 << " ";}cout << endl;vecs_add.insert(vecs_add.end(), iter.begin(), iter.end());}sort(vecs_add.begin(), vecs_add.end());//打印合并之后cout << "-----------------------------------After the merger is------------------------------" << endl;for (auto& iter1 : vecs_add){cout << iter1 << " ";}cout << endl;//vector<vector<int>*> vec_temp;for (auto& iter : vecs)vec_temp.push_back(&iter);vector<int> vec_find = { 1, 3 };//要尋找的位置auto ret0 = FindSortedArrays(vec_temp, vec_find);//打印查找結果cout << "-----------------------------------Find results------------------------------" << endl;for (int i = 0; i != ret0.size(); ++i){cout << "index " << vec_find[i] << " is " << ret0[i] << endl;}//auto ret1 = FindMedian(vec_temp);//打印中位數cout << "-----------------------------------Median is------------------------------" << endl;if (ret1.size() == 1){cout << ret1[0] << endl;}else if (ret1.size() == 2){//轉為小數cout << float(ret1[0] + ret1[1]) * 0.5f << endl;}else{cout << "error" << endl;}} }

?

總結

以上是生活随笔為你收集整理的【LeetCode】4.寻找两个正序数组的中位数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。