LeetCode321拼接数

给定长度分别为 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;
}
};