Интервью Вопрос ... Попытка решить это, но не может найти эффективное решение

Question

Я застрял в одном вопросе интервью .. Вопрос в том,

* дано два массива A и B. A имеет несортированные целые числа. B имеет то же самое длина, как и его значения в набор {-1,0,1}

вы должны вернуть массив C с следующая обработка на А.

если B [i] имеет 0, то C [i] должен иметь A [i]
если B [i] имеет -1, то A [i] должен быть в C внутри подмассива C [0] - C [i-1] т.е. левый подмассив
если B [i] имеет 1, то A [i] должен быть в C внутри подмассива C [i + 1] - 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 ] = -1C[ j ] = A[ i ], где 0 <= j < i - это наименьший индекс, для которого C[ j ] все еще пуст.Если такого индекса нет, ответ невозможен.4. Пройдите массив справа налево , и для каждого i, куда положите B[ i ] = 1C[ j ] = A[ i ], где i < j < n - индекс наибольшего , для которого C[ j ] все еще пуст.Если такого индекса нет, ответ невозможен.

Почему мы помещаем A [i] в ​​крайнее левое положение на шаге 2?Ну, мы знаем, что мы должны поставить его в какую-то позицию j A: [ 1, 2, 3 ] B: [ 1, 1,-1 ] Изначально C пусто: C:[ _, _, _ ]У нас нет 0-х, поэтому давайте перейдем к шагу 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-х в B3. Поместите 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;
}

Answer 2

Это может быть уменьшено до сетевого потока. Вот как можно создать гаджет:

1. Для каждого элемента i из A создайте узел a_i и добавьте ребро емкости устройства от источника к a_i.

2. Для каждого элемента i из C создайте узел c_i и добавьте ребро емкости единицы из c_i в приемник.

3. Для всех 0 значений в B с индексом i добавьте ребро от a_i до c_i, снова с единицей емкости.

4. Для всех значений -1 в B с индексом i добавьте ребро из a_j в c_i, где 0 <= j <i. </p>

5. Для всех 1 в B с индексом i добавьте ребро из a_j в c_i, где i

Пример гаджета:

   a_0 *----* c_0
      / \    \
     /   \    \
    /     |    \
   /  a_1 | c_1 \
S *----*  | *----* T
   \    \ \/    /
    \    \/\   /
     \   /\ | /
      \ /  \|/
       *    *
      a_2   c_2


  B = [ 0, 1, -1]

Максимальный поток в этой сети с пропускной способностью = n соответствует назначению a для c. Чтобы получить перестановку, просто вычислите минимальный срез сети.

Answer 3

Слишком много времени потрачено:; -)

#include <stdint.h>
#include <string.h>
#include <stdio.h>
static int doit(int A[], int B[], int C[], size_t size)
{
    size_t first_free = size - 1;
    size_t last_free = 0;
    for (size_t i = 0; i < size; ++i) {
        if (B[i]) {
            if (i < first_free) {
                first_free = i;
            }
            if (i >= last_free) {
                last_free = i;
            }
        }
    }
    for (int i = 0; i < size; ++i) {
        if (B[i] < 0) {
            if (first_free >= i) {
                return 0;
            }
            C[first_free] = A[i];
            first_free = i;
        } else if (B[i] == 0) {
            C[i] = A[i];
        }
    }
    for (int i = size - 1; i >= 0; --i) {
        if (B[i] > 0) {
            if (last_free <= i) {
                return 0;
            }
            C[last_free] = A[i];
            last_free = i;
        }
    }
    return 1;
}
int a[] = { 1, 2, 3 };
int b[] = { 1, -1, -1 };
int c[sizeof(a) / sizeof(int)];
int main(int argc, char **argv)
{
    if (!doit(a, b, c, sizeof(a) / sizeof(int))) {
        printf("no solution");
    } else {
        for (size_t i = 0; i < sizeof(a) / sizeof(int); ++i)
            printf("c[%zu] = %d\n", i, c[i]);
    }
}

Answer 4

Вот решение с одним внешним проходом.Когда i переходит от 0 к n-1, j переходит к n-1 к 0.Индексы l и r указывают на первое доступное «гибкое» пятно (где b[i] != 0).Если в любой точке l пройдет r, то больше не будет свободных гибких точек, и в следующий раз b[i] != 0 внешняя петля преждевременно разорвется с «отсутствием решения».

Казалось, чтобыть точным, но если в некоторых случаях произойдет сбой, то для исправления будет достаточно добавить еще несколько условий в циклы, которые улучшают гибкие индексы.

Существует постороннее назначение (когда b[i] == 0, c будут установлены как i, так и j), но это безвредно.(То же самое касается l > r чека.)

#include <stdio.h>

#define EMPTY 0 

int main()
{
  int a[] = {1, 2, 3};
  int b[] = {1, -1, -1};
  int c[] = {EMPTY, EMPTY, EMPTY};

  int n = sizeof(a) / sizeof(int);

  int l = 0, r = n - 1;
  int i, j;

  /* Work from both ends at once.
   *   i = 0 .. n-1
   *   j = n-1 .. 0
   *   l = left most free "flex" (c[i] != 0)  slot
   *   r = right most free flex slot
   *
   *   if (l > r) then there are no more free flex spots
   *
   *   when going right with i, check for -1 values
   *   when going left with j, check for 1 values
   *   ... but only after checking for 0 values
   */

  for (i = 0, j = n - 1; i < n; ++i, --j)
  {
    /* checking i from left to right... */
    if (b[i] == 0)
    {
      c[i] = a[i];

      /* advance l to the next free spot */
      while (l <= i && c[l] != EMPTY) ++l;
    }
    else if (b[i] == -1)
    {
      if (i <= l) break;

      c[l] = a[i];

      /* advance l to the next free spot, 
       * skipping over anything already set by c[i] = 0 */
      do ++l; while (l <= i && c[l] != EMPTY);
    }

    /* checking j from right to left... */
    if (b[j] == 0)
    {
      c[j] = a[j];
      while (r >= j && c[r] != EMPTY) --r;
    }
    else if (b[j] == 1)
    {
      if (j >= r) break;

      c[r] = a[j];
      do --r; while (r >= j && c[r] != EMPTY);
    }

    if (l > r)
    {
      /* there cannot be any more free flex spots, so
         advance l,r to the end points. */
      l = n;
      r = -1;
    }
  }

  if (i < n)
    printf("Unsolvable");
  else
  {
    for (i = 0; i < n; ++i)
      printf("%d ", c[i]);
  }

  printf("\n");

  return 0;
}