Organizar números para formar una secuencia válida

Dada una array arr[] con N números distintos y otra array arr1[] con N-1 operadores (ya sea < o >), la tarea es organizar los números para formar una secuencia válida que obedezca las reglas de los operadores relacionales con respecto a los operadores proporcionados. .

Ejemplos: 

Entrada: arr[] = {3, 12, 7, 8, 5}; arr1= {‘<‘, ‘>’, ‘>’, ‘<‘} 
Salida: {3, 12, 8, 5, 7} 
Explicación: 
3 < 12 > 8 > 5 < 7 
Puede haber más combinaciones de este tipo. La tarea es devolver una de las combinaciones.

Entrada: arr[] = {8, 2, 7, 1, 5, 9}; arr1[] = {‘>’, ‘>’, ‘<‘, ‘>’, ‘<‘} 
Salida: {9, 8, 1, 7, 2, 5} 
Explicación: 
9 > 8 > 1 < 7 > 2 < 5 
 

Enfoque ingenuo: 
un enfoque ingenuo consiste en probar todas las diferentes disposiciones posibles de números y comprobar si la secuencia es válida.
Complejidad temporal: O(2 ^N ).

Enfoque eficiente: la idea es ordenar primero la array dada de números en orden ascendente. Luego resuelve el problema usando la técnica de dos punteros : uno apuntando al frente y otro apuntando al final.  

1. Tome una array resultante del mismo tamaño que la array dada.
2. Si el operador actual es ‘<‘, incluya el elemento al que apunta el puntero superior en la array resultante e increméntelo en 1.
3. Si el operador actual es ‘>’, incluya el elemento al que apunta el último puntero en la array resultante y disminuya en 1.

A continuación se muestra la implementación del enfoque anterior.  

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to organize the given numbers
// to form a valid sequence.
vector<int> orgazineInOrder(vector<int> vec,
                            vector<int> op, int n)
{
    vector<int> result(n);
    // Sorting the array
    sort(vec.begin(), vec.end());
 
    int i = 0, j = n - 1, k = 0;
    while (i <= j && k <= n - 2) {
        // Two pointer technique
        // to organize the numbers
        if (op[k] == '<') {
            result[k] = vec[i++];
        }
        else {
            result[k] = vec[j--];
        }
        k++;
    }
    result[n - 1] = vec[i];
 
    return result;
}
 
// Driver code
int main()
{
    vector<int> vec({ 8, 2, 7, 1, 5, 9 });
 
    vector<int> op({ '>', '>', '<',
                     '>', '<' });
 
    vector<int> result
        = orgazineInOrder(vec,
                          op, vec.size());
 
    for (int i = 0; i < result.size(); i++) {
        cout << result[i] << " ";
    }
    return 0;
}

// Java implementation of the above approach
import java.util.*;
 
class GFG
{
 
// Function to organize the given numbers
// to form a valid sequence.
static int[] orgazineInOrder(int []vec,int[] op, int n)
{
    int []result = new int[n];
     
    // Sorting the array
    Arrays.sort(vec);
 
    int i = 0, j = n - 1, k = 0;
    while (i <= j && k <= n - 2)
    {
        // Two pointer technique
        // to organize the numbers
        if (op[k] == '<')
        {
            result[k] = vec[i++];
        }
        else
        {
            result[k] = vec[j--];
        }
        k++;
    }
    result[n - 1] = vec[i];
 
    return result;
}
 
// Driver code
public static void main(String[] args)
{
    int []vec ={ 8, 2, 7, 1, 5, 9 };
 
    int[] op ={ '>', '>', '<',
                    '>', '<' };
 
    int []result = orgazineInOrder(vec,
                        op, vec.length);
 
    for (int i = 0; i < result.length; i++)
    {
        System.out.print(result[i]+ " ");
    }
}
}
 
// This code is contributed by 29AjayKumar

# Python3 implementation of the above approach
 
# Function to organize the given numbers
# to form a valid sequence.
def orgazineInOrder(vec, op, n) :
 
    result = [0] * n;
     
    # Sorting the array
    vec.sort();
    i = 0;
    j = n - 1;
    k = 0;
     
    while (i <= j and k <= n - 2) :
         
        # Two pointer technique
        # to organize the numbers
        if (op[k] == '<') :
            result[k] = vec[i];
            i += 1;
         
        else :
            result[k] = vec[j];
            j -= 1;
         
        k += 1;
 
    result[n - 1] = vec[i];
 
    return result;
 
# Driver code
if __name__ == "__main__" :
 
    vec = [ 8, 2, 7, 1, 5, 9 ];
    op = [ '>', '>', '<', '>', '<' ];
 
    result = orgazineInOrder(vec, op, len(vec));
 
    for i in range(len(result)) :
        print(result[i], end = " ");
 
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
 
class GFG
{
     
    // Function to organize the given numbers
    // to form a valid sequence.
    static int[] orgazineInOrder(int []vec,int[] op, int n)
    {
        int []result = new int[n];
         
        // Sorting the array
        Array.Sort(vec);
     
        int i = 0, j = n - 1, k = 0;
        while (i <= j && k <= n - 2)
        {
            // Two pointer technique
            // to organize the numbers
            if (op[k] == '<')
            {
                result[k] = vec[i++];
            }
            else
            {
                result[k] = vec[j--];
            }
            k++;
        }
        result[n - 1] = vec[i];
     
        return result;
    }
     
    // Driver code
    public static void Main()
    {
        int []vec ={ 8, 2, 7, 1, 5, 9 };
     
        int[] op ={ '>', '>', '<',
                        '>', '<' };
     
        int []result = orgazineInOrder(vec,
                            op, vec.Length);
     
        for (int i = 0; i < result.Length; i++)
        {
            Console.Write(result[i] + " ");
        }
    }
}
 
// This code is contributed by AnkitRai01

<script>
 
// Javascript implementation of the above approach
 
// Function to organize the given numbers
// to form a valid sequence.
function orgazineInOrder(vec, op, n)
{
    let result = [n];
     
    // Sorting the array
    vec.sort();
 
    let i = 0, j = n - 1, k = 0;
     
    while (i <= j && k <= n - 2)
    {
         
        // Two pointer technique
        // to organize the numbers
        if (op[k] == '<')
        {
            result[k] = vec[i++];
        }
        else
        {
            result[k] = vec[j--];
        }
        k++;
    }
    result[n - 1] = vec[i];
 
    return result;
}
 
// Driver code
let vec = [ 8, 2, 7, 1, 5, 9 ];
let op = [ '>', '>', '<', '>', '<' ];
 
let result = orgazineInOrder(vec,
                             op, vec.length);
 
for(let i = 0; i < result.length; i++)
{
   document.write(result[i] + " ");
}
 
// This code is contributed by sravan kumar
 
</script>

9 8 1 7 2 5

Complejidad de tiempo: O (NlogN)

Espacio Auxiliar: O(N)