是否有任何有效的方法从两个数组的交替元素中获得最长可能的排序数组?

Question

示例:N = 5, M = 4

=[4, 2、10、5、9]

B =(4、5、6、15)

所以最长的排序数组之一是[2,4,5,6,9,15]

这是我的方法，但想知道是否有任何有效的方法可用。我可以保证这不是来自任何在线编程比赛，这是在面试中被问到的，所以我想知道有效的方法，如果有的话。

#include<bits/stdc++.h> 
using namespace std; 
int mx=0;
void generateUtil(int A[], int B[], int C[], int i, int j, int m, int n, 
int len, bool flag) 
{ 
if (flag) 
{ 
if (len) 
mx=max(mx,len+1); 
for (int k = i; k < m; k++) 
{ 
if (!len) 
{ 
C[len] = A[k];
generateUtil(A, B, C, k+1, j, m, n, len, !flag); 
} 
{ 
if (A[k] > C[len]) 
{ 
C[len+1] = A[k]; 
generateUtil(A, B, C, k+1, j, m, n, len+1, !flag); 
} 
} 
} 
} 
{ 
for (int l = j; l < n; l++) 
{ 
if (B[l] > C[len]) 
{ 
C[len+1] = B[l]; 
generateUtil(A, B, C, i, l+1, m, n, len+1, !flag); 
} 
} 
} 
} 
void generate(int A[], int B[], int m, int n) 
{ 
int C[m+n];
generateUtil(A, B, C, 0, 0, m, n, 0, true); 
} 
int main() 
{ 
int n,m,i,j;
cin>>n>>m;
int A[n],B[m];
for(i=0;i<n;i++)
{
cin>>A[i];
}
for(j=0;j<n;j++)
{
cin>>B[j];
}
generate(A, B, n, m); 
cout<<mx<<"n";
return 0; 
} 

Answer 1

这取决于你对效率的定义。如果我们要测量代码长度、容易理解程度和bug的可能性，这是非常有效的:

#include <algorithm>
#include <iterator>
#include <set>
std::set<int> result;
std::copy(std::begin(A), std::end(A), std::inserter(result, result.end()));
std::copy(std::begin(B), std::end(B), std::inserter(result, result.end()));
for (int e : result) { std::cout << e << ' '; }

还有:为什么我不能#include ?编辑:

看起来这实际上并没有按照要求去做。虽然在这一点上，我不知道是什么问题。

Answer 2

下面使用标准算法库。至于这是否是你的雇主想要的，这是一个悬而未决的问题!

#include <algorithm>
#include <iostream>
#include <iterator>
int main()
{
int A[] = {4,2,10,5,9};
int B[] = {4,5,6,15};
std::sort(std::begin(A), std::end(A));
std::sort(std::begin(B), std::end(B));
int C [std::size(A) + std::size(B)];
std::merge(std::begin(A), std::end(A),std::begin(B), std::end(B),C);
// std::unique will return one after last valid element
auto iter = std::unique(std::begin(C), std::end(C));
for ( auto p = std::begin(C); p != iter; ++p){
std::cout << *p << ",n";
}
}