题目
给定长度分别为 m 和 n 的两个数组，其元素由 0-9 构成，表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。
求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。
说明: 请尽可能地优化你算法的时间和空间复杂度。
示例 1:
输入:
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
输出:
[9, 8, 6, 5, 3]
示例 2:
输入:
nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
输出:
[6, 7, 6, 0, 4]
示例 3:
输入:
nums1 = [3, 9]
nums2 = [8, 9]
k = 3
输出:
[9, 8, 9]
2023年3月版
class Solution { public: vector maxNumber(vector& nums1, vector& nums2, int k) { vector vRet; for (int iLeft = 0; iLeft <= k; iLeft++) { const vector v1 = maxNumber(nums1, iLeft); const vector v2 = maxNumber(nums2, k - iLeft); if (v1.size() + v2.size() != k) { continue; } vector nums; auto it1 = v1.begin(); auto it2 = v2.begin(); while ((it1 != v1.end() ) && (it2 != v2.end() )) { if (*it1 > *it2 ) { nums.push_back(*it1); it1++; } else if(*it1 < *it2) { nums.push_back(*it2); it2++; } else { if (Less(it1, v1.end(), it2, v2.end())) { nums.push_back(*it2); it2++; } else { nums.push_back(*it1); it1++; } } } std::copy(it1, v1.end(), std::back_inserter(nums)); std::copy(it2, v2.end(), std::back_inserter(nums)); if ((vRet.size() == 0) || Less(vRet,nums)) { vRet.swap(nums); } } return vRet; } template bool Less(IT itBegin1, IT itEnd1, IT itBegin2, IT itEnd2) { while ((itBegin1 != itEnd1) && (itBegin2 != itEnd2)) { if (*itBegin1 < *itBegin2) { return true; } else if (*itBegin1 > *itBegin2) { return false; } itBegin1++; itBegin2++; } return itBegin1 == itEnd1; } bool Less(const vector& v1, const vector& v2) { for (int i = 0; i < v1.size(); i++) { if (v1[i] < v2[i]) { return true; } else if (v1[i] > v2[i]) { return false; } } return false; } vector maxNumber(const vector& nums, int k) { vector ret; for (int i = 0; i < nums.size(); i++) { const int& n = nums[i]; while (ret.size() && (n > ret.back()) && ((ret.size() + nums.size() - i - 1) >= k)) { ret.pop_back(); } if (ret.size() < k) { ret.push_back(n); } } return ret; } };
2023年8月
template<class T = int,class _Pr = std::less > class CTopK { public: CTopK(int k):m_iMinNum(k) { } void Do(vector& m_v,T* begin, int num) { for (; num ; begin++,num–) { while (m_v.size() && _Pr()( *begin, m_v.back()) && (m_iMinNum - m_v.size()+1 <= num)) { m_v.pop_back(); } if (m_v.size() < m_iMinNum) { m_v.push_back(*begin); } } } protected: const int m_iMinNum; }; class Solution { public: vector maxNumber(vector& nums1, vector& nums2, int k) { CTopK<int,std::greater> tok(k); vector<vector> vNums1(k + 1), vNums2(k + 1); tok.Do(vNums1[k], nums1.data(), nums1.size()); tok.Do(vNums2[k], nums2.data(), nums2.size()); for (int i = k - 1; i >0; i–) { CTopK<int, std::greater> tok(i); tok.Do(vNums1[i], vNums1[i + 1].data(), vNums1[i + 1].size()); tok.Do(vNums2[i], vNums2[i + 1].data(), vNums2[i + 1].size()); } vector vRet(k); for (int i = max(0,k-(int)nums2.size()); i <= min(k,(int)nums1.size()); i++) { const auto& v1 = vNums1[i]; const auto& v2 = vNums2[k - i]; vector cur; auto it = v1.begin(); auto ij = v2.begin(); while ((it != v1.end()) || (ij != v2.end())) { bool b = lexicographical_compare(it, v1.end(), ij, v2.end()); if (b) { cur.emplace_back((ij++)); } else { cur.emplace_back((it++)); } } if (cur > vRet) { vRet.swap(cur); } } return vRet; } };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《闻缺陷则喜算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 鄙人想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 墨家名称的来源：有所得以墨记之。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
