时间戳

首页 > 解决方案 > 有没有什么有效的方法可以从两个数组的交替元素中获得最长的排序数组？

c++ - 有没有什么有效的方法可以从两个数组的交替元素中获得最长的排序数组？

问题描述

例如：N=5，M=4

A=[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; 
}

标签： c++

解决方案

取决于你所说的高效。如果我们测量代码长度、易于理解和错误的可能性，这是非常有效的：

#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 <bits/stdc++.h>？.

编辑：这似乎并没有真正做到所要求的。虽然在这一点上我不知道被问到什么。

推荐阅读