Consultas para buscar un elemento en una array y modificar la array según las condiciones dadas

Dada una array arr[] que consta de N enteros y un entero X , la tarea es imprimir la array después de realizar X consultas indicadas por una array de operaciones[] . La tarea para cada consulta es la siguiente:

• Si la array contiene las operaciones enteras [i] , invierta la subarreglo comenzando desde el índice en el que se encuentran las operaciones [i] hasta el final de la array.
• De lo contrario, inserte operaciones[i] al final de la array.

Ejemplos:

Entrada: arr[] = {1, 2, 3, 4}, X = 3, operaciones[] = {12, 2, 13}
Salida: 1 12 4 3 2
Explicación:  
Consulta 1: arr[] no contiene 12 Por lo tanto, agréguelo al último. Por lo tanto, arr[] = {1, 2, 3, 4, 12}. 
Consulta 2: arr[] contiene 2 en el índice 1. Por lo tanto, invierta el subarreglo {arr[1], arr[4]} . Por lo tanto, arr[] = {1, 12, 4, 3, 2}. 
Consulta 3: arr[] no contiene 13. Por lo tanto, agréguelo al último. Por lo tanto, arr[] = {1, 12, 4, 3, 2, 13}.

Entrada: arr[] = {1, 1, 12, 6}, X = 2, operaciones[] = {1, 13}
Salida: 1 12 4 3 2

Enfoque: el enfoque más simple es que para cada consulta busque en toda la array para verificar si el entero en cuestión está presente o no. Si está presente en un índice i y el tamaño actual de la array es N , invierta el subarreglo {arr[i], … arr[N – 1]} . De lo contrario, inserte el elemento buscado al final de la array. Siga los pasos a continuación para resolver el problema:

1. Cree una función para buscar linealmente el índice de un elemento en una array.
2. Ahora, para cada consulta, si el elemento dado no está presente en la array dada, agréguelo al final de la array.
3. De lo contrario, si está presente en cualquier índice i , invierta el subarreglo desde el índice i hasta el final .
4. Después de completar los pasos anteriores, imprima la array resultante.

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

// C++ program for the above approach
#include<bits/stdc++.h>
using namespace std;
 
// Function to reverse the subarray
// over the range [i, r]
void rev(vector<int> &arr, int l, int r)
{
     
    // Iterate over the range [l, r]
    while (l < r)
    {
        int tmp = arr[l];
        arr[l] = arr[r];
        arr[r] = tmp;
        l++;
        r--;
    }
}
 
// Function that perform the given
// queries for the given array
void doOperation(vector<int> &arr, int o)
{
     
    // Search for the element o
    int ind = -1;
 
    // Current size of the array
    int n = arr.size();
 
    for(int i = 0; i < n; i++)
    {
         
        // If found, break out of loop
        if (arr[i] == o)
        {
            ind = i;
            break;
        }
    }
 
    // If not found, append o
    if (ind == -1)
        arr.push_back(o);
 
    // Otherwise, reverse the
    // subarray arr[ind] to arr[n - 1]
    else
        rev(arr, ind, n - 1);
}
 
// Function to print the elements
// in the vector arr[]
void print(vector<int> &arr)
{
     
    // Traverse the array arr[]
    for(int x : arr)
    {
         
        // Print element
        cout << x << " ";
    }
}
 
// Function to perform operations
void operations(vector<int> &queries,
                vector<int> &arr)
{
    for(auto x : queries)
        doOperation(arr, x);
}
 
// Driver Code
int main()
{
     
    // Given array arr[]
    int arr[] = { 1, 2, 3, 4 };
    int x = 3;
 
    // Given queries
    vector<int> queries({ 12, 2, 13 });
 
    // Add elements to the vector
    vector<int> arr1;
 
    for(int z : arr)
        arr1.push_back(z);
 
    // Perform queries
    operations(queries, arr1);
 
    // Print the resultant array
    print(arr1);
}
 
// This code is contributed by SURENDRA_GANGWAR

// Java program for the above approach
 
import java.io.*;
import java.util.*;
 
class GFG {
 
    // Function that perform the given
    // queries for the given array
    static void doOperation(
        ArrayList<Integer> arr, int o)
    {
 
        // Search for the element o
        int ind = -1;
 
        // Current size of the array
        int n = arr.size();
 
        for (int i = 0; i < n; i++) {
 
            // If found, break out of loop
            if (arr.get(i) == o) {
                ind = i;
                break;
            }
        }
 
        // If not found, append o
        if (ind == -1)
            arr.add(o);
 
        // Otherwise, reverse the
        // subarray arr[ind] to arr[n - 1]
        else
            reverse(arr, ind, n - 1);
    }
 
    // Function to reverse the subarray
    // over the range [i, r]
    static void reverse(
        ArrayList<Integer> arr, int l,
        int r)
    {
        // Iterate over the range [l, r]
        while (l < r) {
            int tmp = arr.get(l);
            arr.set(l, arr.get(r));
            arr.set(r, tmp);
            l++;
            r--;
        }
    }
 
    // Function to print the elements
    // in the ArrayList arr[]
    static void print(ArrayList<Integer> arr)
    {
        // Traverse the array arr[]
        for (int x : arr) {
 
            // Print element
            System.out.print(x + " ");
        }
    }
 
    // Function to perform operations
    static void operations(
        int queries[],
        ArrayList<Integer> arr)
    {
        for (int x : queries)
            doOperation(arr, x);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Given array arr[]
        int arr[] = { 1, 2, 3, 4 };
        int x = 3;
 
        // Given queries
        int queries[] = { 12, 2, 13 };
 
        // Add elements to the arraylist
        ArrayList<Integer> arr1
            = new ArrayList<>();
 
        for (int z : arr)
            arr1.add(z);
 
        // Perform queries
        operations(queries, arr1);
 
        // Print the resultant array
        print(arr1);
    }
}

# Python3 program for
# the above approach
 
# Function to reverse the
# subarray over the range
# [i, r]
def rev(arr, l, r):
 
    # Iterate over the
    # range [l, r]
    while (l < r):
        arr[l], arr[r] = (arr[r],
                          arr[l])
        l += 1
        r -= 1
 
# Function that perform the given
# queries for the given array
def doOperation(arr, o):
 
    # Search for the
    # element o
    ind = -1
 
    # Current size of
    # the array
    n = len(arr)
 
    for i in range(n):
 
        # If found, break out
        # of loop
        if (arr[i] == o):
 
            ind = i
            break
 
    # If not found, append o
    if (ind == -1):
        arr.append(o)
 
    # Otherwise, reverse the
    # subarray arr[ind] to
    # arr[n - 1]
    else:
        rev(arr,
            ind, n - 1)
 
# Function to print the
# elements in the vector
# arr[]
def print_array(arr):
 
    # Traverse the
    # array arr[]
    for x in arr:
 
        # Print element
        print(x, end = " ")
 
# Function to perform
# operations
def operations(queries, arr):
 
    for x in queries:
        doOperation(arr, x)
 
# Driver Code
if __name__ == "__main__":
 
    # Given array arr[]
    arr = [1, 2, 3, 4]
    x = 3
 
    # Given queries
    queries = [12, 2, 13]
 
    # Add elements to the vector
    arr1 = []
 
    for z in arr:
        arr1.append(z)
 
    # Perform queries
    operations(queries, arr1)
 
    # Print the resultant array
    print_array(arr1)
 
# This code is contributed by Chitranayal

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function that perform the given
// queries for the given array
static void doOperation(List<int> arr, int o)
{
     
    // Search for the element o
    int ind = -1;
 
    // Current size of the array
    int n = arr.Count;
 
    for(int i = 0; i < n; i++)
    {
         
        // If found, break out of loop
        if (arr[i] == o)
        {
            ind = i;
            break;
        }
    }
 
    // If not found, append o
    if (ind == -1)
        arr.Add(o);
 
    // Otherwise, reverse the
    // subarray arr[ind] to arr[n - 1]
    else
        reverse(arr, ind, n - 1);
}
 
// Function to reverse the subarray
// over the range [i, r]
static void reverse(List<int> arr, int l,
                                   int r)
{
     
    // Iterate over the range [l, r]
    while (l < r)
    {
        int tmp = arr[l];
        arr[l] = arr[r];
        arr[r] =  tmp;
        l++;
        r--;
    }
}
 
// Function to print the elements
// in the List []arr
static void print(List<int> arr)
{
     
    // Traverse the array []arr
    foreach(int x in arr)
    {
 
        // Print element
        Console.Write(x + " ");
    }
}
 
// Function to perform operations
static void operations(int []queries,
                       List<int> arr)
{
    foreach(int x in queries)
        doOperation(arr, x);
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given array []arr
    int []arr = { 1, 2, 3, 4 };
    //int x = 3;
 
    // Given queries
    int []queries = { 12, 2, 13 };
 
    // Add elements to the arraylist
    List<int> arr1 = new List<int>();
 
    foreach (int z in arr)
        arr1.Add(z);
 
    // Perform queries
    operations(queries, arr1);
 
    // Print the resultant array
    print(arr1);
}
}
 
// This code is contributed by gauravrajput1

<script>
 
// Javascript program for the above approach
 
// Function that perform the given
// queries for the given array
function doOperation(arr, o)
{
     
    // Search for the element o
    let ind = -1;
 
    // Current size of the array
    let n = arr.length;
 
    for(let i = 0; i < n; i++)
    {
         
        // If found, break out of loop
        if (arr[i] == o)
        {
            ind = i;
            break;
        }
    }
 
    // If not found, append o
    if (ind == -1)
        arr.push(o);
 
    // Otherwise, reverse the
    // subarray arr[ind] to arr[n - 1]
    else
        reverse(arr, ind, n - 1);
}
 
// Function to reverse the subarray
// over the range [i, r]
function reverse(arr, l, r)
{
     
    // Iterate over the range [l, r]
    while (l < r)
    {
        let tmp = arr[l];
        arr[l] = arr[r];
        arr[r] = tmp;
        l++;
        r--;
    }
}
 
// Function to print the elements
// in the ArrayList arr[]
function print(arr)
{
    document.write(arr.join(" "));
}
 
// Function to perform operations   
function operations(queries, arr)
{
    for(let x = 0; x < queries.length; x++)
        doOperation(arr, queries[x]);
}
 
// Driver Code
let arr = [ 1, 2, 3, 4 ];
let x = 3;
 
// Given queries
let queries = [ 12, 2, 13 ];
 
// Perform queries
operations(queries, arr);
 
// Print the resultant array
print(arr);
 
// This code is contributed by avanitrachhadiya2155
 
</script>

1 12 4 3 2 13 

Complejidad de tiempo: O(N*X) donde N es el tamaño de la array dada y X es el número de consultas.
Espacio Auxiliar: O(N)