面试问题......试图解决,但无法获得有效的解决方案

Question

我被困在一个面试问题中..问题是,

*给定两个数组A和B.A的整数未排序.B与A具有相同的长度,其值在集合{-1,0,1}中

你必须返回一个数组C,在A上进行以下处理.

如果B [i]为0则C [i]必须有A [i]
如果B [i]有-1则A [i]必须在子数组C [0]中的C中 - C [i-1]即.
如果B [i]具有1则左子阵列则A [i]必须在子阵列C [i + 1]中的C中 - C [长度(A)]即右子阵列.

如果不存在这样的解决方案那么printf("没有解决方案");*

我应用了以下逻辑: -

int indMinus1 = n-1;
int indPlus1 = 0;

//while(indPlus1 < n && indMinus1 > 0)
while(indPlus1 < indMinus1)
{
    while(b[indMinus1] != -1)   {
        if(b[indMinus1] == 0)
            c[indMinus1] = a[indMinus1];
        indMinus1--;
    }
    while(b[indPlus1] != +1)    {
        if(b[indPlus1] == 0)
            c[indPlus1] = a[indPlus1];
        indPlus1++;
    }

    c[indMinus1] = a[indPlus1];
    c[indPlus1] = a[indMinus1];
    b[indMinus1] = 0;
    b[indPlus1] = 0;
    indMinus1--;
    indPlus1++;
}

但这不会起作用,对于像{1,2,3} >> {1,-1,-1}这样的情况......一个输出是可能的,即{2,3,1};

请帮助....他们的任何算法技术可用于此问题吗？

正确的解决方案代码

int arrange(int a[], int b[], int c[], int n)
{

for (int i = 0; i < n; ++i) {
    if(b[i] == 0)
        c[i] = a[i];
}

int ci = 0;
for (int i = 0; i < n; ++i) {
    if(b[i] == -1)  {
        while(c[ci] != 0 && ci < i)
            ci ++;
        if(c[ci] != 0 || ci >= i)
            return -1;
        c[ci] = a[i];
        ci++;
    }
}

for (int i = 0; i < n; ++i) {
    if(b[i] == 1)   {
        while(c[ci] != 0 && ci < n)
            ci ++;
        if(c[ci] != 0 || ci <= i)
            return -1;
        c[ci] = a[i];
        ci++;
    }
    }
    return 0;
}

Answer 1

我建议使用以下算法:
1.最初将所有算法C[ i ]视为空巢.
2.对于每一个我在哪里B[ i ] = 0,我们就把C[ i ] = A[ i ]
3.经过阵列由左到右,并为每个i地方B[ i ] = -1放
C[ j ] = A[ i ],那里0 <= j < i是最小的指数,其C[ j ]仍然是空的.如果不存在这样的索引,则答案是不可能的.
4.通过数组去从右到左,并为每个i地方B[ i ] = 1放
C[ j ] = A[ i ],那里i < j < n是最大的指数,其C[ j ]仍然是空的.如果不存在这样的索引,则答案是不可能的.

为什么我们在步骤2中将A [i]放在最左边的位置？好吧,我们知道我们必须把它放到某个位置j <i.另一方面,将它放在最左边将增加我们的更改,以免在第3步中陷入困境.请参阅此示例以进行说明:

A: [ 1, 2, 3 ]
B: [ 1, 1,-1 ]

最初C是空的:C:[ _, _, _ ]
我们没有0-s,所以让
我们转到第2步.我们必须选择是否将元素放置A[ 2 ]到C[ 0 ]或C[ 1 ].
如果我们把它并不是最左边,我们会得到下面的情况:
C: [ _, 3, _ ]
还有......哎呀,我们无法安排元素A[ 0 ],并A[ 1 ]因不足之处:(
但是,如果我们把A [2]最左边,我们会得到
C: [ 3, _, _ ],而且它非常有可能完成算法
C: [ 3, 1, 2 ]:)

复杂性:
我们所做的是沿着数组传递三次,因此复杂性是O(3n) = O(n)- 线性的.

进一步举例:

A: [ 1, 2, 3 ]
B: [ 1, -1, -1 ]

让我们通过算法分步:
1. C: [ _, _, _ ]
2.空,因为没有0-S中B
3把A[ 1 ]和A[ 2 ]最左边的空位置:

C: [ 2, 3, _ ]

4.将A[ 0 ]最右边的自由位置(在此示例中为唯一一个)自由位置:

C: [ 2, 3, 1 ]

这是答案.

源代码:

#include <iostream>
#include <string>
#include <vector>

using namespace std;


vector< int > a;
vector< int > b;
vector< int > c;
int n;

bool solve ()
{
    int i;
    for( i = 0; i < n; ++i )
        c[ i ] = -1;
    for( i = 0; i < n; ++i )
        if( b[ i ] == 0 )
            c[ i ] = a[ i ];
    int leftmost = 0;
    for( i = 0; i < n; ++i )
        if( b[ i ] == -1 )
        {
            for( ; leftmost < i && c[ leftmost ] != -1; ++leftmost ); // finding the leftmost free cell
            if( leftmost >= i )
                return false; // not found
            c[ leftmost++ ] = a[ i ];
        }
    int rightmost = n - 1;
    for( i = n - 1; i >= 0; --i )
        if( b[ i ] == 1 )
        {
            for( ; rightmost > i && c[ rightmost ] != -1; --rightmost ); // finding the rightmost free cell
            if( rightmost <= i )
                return false; // not found;
            c[ rightmost-- ] = a[ i ];
        }
    return true;
}


int main ()
{
    cin >> n;
    a.resize(n);
    b.resize(n);
    c.resize(n);
    int i;
    for( i = 0; i < n; ++i )
        cin >> a[ i ];
    for( i = 0; i < n; ++i )
        cin >> b[ i ];
    if( !solve() )
        cout << "Impossible";
    else
        for( i = 0; i < n; ++i )
            cout << c[ i ] << ' ';
    cout << endl;
    return 0;
}