Encuentre el índice de los elementos de la array después de realizar operaciones dadas K veces

Dada una array arr[] y un entero K , la tarea es imprimir la posición de los elementos de la array, donde el i -ésimo valor en el resultado es el índice del i -ésimo elemento en la array original después de aplicar las siguientes operaciones exactamente K veces :

  • Elimine el primer elemento de la array y disminuya en 1 .
  • Si es mayor que 0 después de disminuir, colóquelo al final de la array y cambie la posición de los elementos a la izquierda.

Ejemplos:

Entrada: arr[] = {3, 1, 3, 2}, K = 4
Salida: {0, 2, 3}
Explicación:
Operación 1 -> arr[] = {3, 1, 3, 2} (posición { 0, 1, 2, 3}) -> {1, 3, 2, 2} (posición {1, 2, 3, 0}).
Operación 2 -> arr[] = {1, 3, 2, 2} (posición {1, 2, 3, 0})-> {3, 2, 2} (posición {2, 3, 0}), ya que el primer elemento se convirtió en cero.
Operación 3 -> arr[] = {3, 2, 2} (posición {2, 3, 0}) -> {2, 2, 2} (posición {3, 0, 2}).
Operación 4 -> ar[] = {2, 2, 2} (posición {3, 0, 2}) -> {2, 2, 1} (posición {0, 2, 3}).

Entrada: arr[] = {1, 2, 3}, K = 3 
Salida: {1, 2} 
Explicación: 
Operación 1 -> arr[] = {1, 2, 3} (posición {0, 1, 2} ) -> {2, 3} (posición {1, 2}).
Operación 2 -> arr[] = {2, 3} (posición {1, 2}) -> {3, 1} (posición {2, 1}), ya que el primer elemento se convirtió en cero.
Operación 3 -> arr[] = {3, 1} (posición {2, 1}) -> {1, 2} (posición {1, 2}).

Enfoque: La idea es utilizar una cola para simular las operaciones K. Siga los pasos a continuación para resolver el problema:

  1. Inicialice una cola para almacenar los pares de {arr[i], i} .
  2. Iterar sobre el rango [0, K – 1] y realizar las siguientes operaciones:
    1. Haga estallar el elemento frontal de la Cola y disminuya su valor en 1 .
    2. Vuelva a colocar el elemento actualizado en la cola.
  3. Utilice el segundo miembro del par para imprimir la posición de los elementos extrayéndolos hasta que la cola esté vacía.

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

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to print position of array
// elements after performing given
// operations exactly K times
void findElementPositions(int arr[], int N, int K)
{
 
    // make the queue of pairs
    queue<pair<int, int> > que;
 
    // Convert the array
    // to queue of pairs
    for (int i = 0; i < N; i++) {
        que.push({ arr[i], i });
    }
 
    // Perform the operations
    // for K units of time
    for (int i = 0; i < K; i++) {
 
        // get the front pair
        pair<int, int> value = que.front();
 
        // If the first element
        // value is one
        if (value.first == 1) {
            que.pop();
        }
 
        // Otherwise
        else {
            que.pop();
            value.first -= 1;
            que.push(value);
        }
    }
 
    // Print all the positions
    // after K operations
    while (!que.empty()) {
 
        pair<int, int> value = que.front();
        que.pop();
 
        cout << value.second << " ";
    }
}
 
// Driven Program
int main()
{
   
    // Given array
    int arr[] = { 3, 1, 3, 2 };
 
    // Stores the length of array
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Given value of K
    int K = 4;
 
    // Function call
    findElementPositions(arr, N, K);
 
    return 0;
}
 
// This code is contributed by Kingash.

Java

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG {
 
  // Function to print position of array
  // elements after performing given
  // operations exactly K times
  static void findElementPositions(int arr[], int N,
                                   int K)
  {
 
    // make the queue of pairs
    ArrayDeque<int[]> que = new ArrayDeque<>();
 
    // Convert the array
    // to queue of pairs
    for (int i = 0; i < N; i++) {
      que.addLast(new int[] { arr[i], i });
    }
 
    // Perform the operations
    // for K units of time
    for (int i = 0; i < K; i++) {
 
      // get the front pair
      int value[] = que.peekFirst();
 
      // If the first element
      // value is one
      if (value[0] == 1) {
        que.pollFirst();
      }
 
      // Otherwise
      else {
        que.pollFirst();
        value[0] -= 1;
        que.addLast(value);
      }
    }
 
    // Print all the positions
    // after K operations
    while (!que.isEmpty())
    {
 
      int value[] = que.pollFirst();
      System.out.print(value[1] + " ");
    }
  }
 
  // Driver code
  public static void main(String[] args)
  {
 
    // Given array
    int arr[] = { 3, 1, 3, 2 };
 
    // length of the array
    int N = arr.length;
 
    // Given value of K
    int K = 4;
 
    // Function call
    findElementPositions(arr, N, K);
  }
}
 
// This code is contributed by Kingash.

Python3

# Python3 program for the above approach
 
# Function to print position of array
# elements after performing given
# operations exactly K times
def findElementPositions(que, K):
 
    # Convert the queue
    # to queue of pairs
    for i in range(len(que)):
        que[i] = [que[i], i]
 
    # Perform the operations
    # for K units of time
    for i in range(K):
 
        # If the first element
        # value is one
        if que[0][0] == 1:
            que.pop(0)
 
        # Otherwise
        else:
            temp = que.pop(0)
            temp[0] -= 1
            que.append(temp)
 
    # All the positions
    # after K operations
    ans = [i[1] for i in que]
 
    # Print the answer
    print(ans)
 
 
# Given array
arr = [3, 1, 3, 2]
 
# Given value of K
K = 4
 
findElementPositions(arr, K)

C#

// C# program for the above approach
using System;
using System.Collections;
class GFG {
     
    // Function to print position of array
    // elements after performing given
    // operations exactly K times
    static void findElementPositions(int[] arr, int N, int K)
    {
      
        // make the queue of pairs
        Queue que = new Queue();
      
        // Convert the array
        // to queue of pairs
        for (int i = 0; i < N; i++) {
            que.Enqueue(new Tuple<int,int>(arr[i], i));
        }
      
        // Perform the operations
        // for K units of time
        for (int i = 0; i < K; i++) {
      
            // get the front pair
            Tuple<int,int> value = (Tuple<int,int>)que.Peek();
      
            // If the first element
            // value is one
            if (value.Item1 == 1) {
                que.Dequeue();
            }
      
            // Otherwise
            else {
                que.Dequeue();
                value = new Tuple<int,int>(value.Item1-1, value.Item2);
                que.Enqueue(value);
            }
        }
      
        // Print all the positions
        // after K operations
        Console.Write("[");
        while (que.Count > 0) {
      
            Tuple<int,int> value = (Tuple<int,int>)que.Peek();
            que.Dequeue();
             
            if(que.Count > 0)
            {
                Console.Write(value.Item2 + ", ");
            }
            else{
                Console.Write(value.Item2);
            }
        }
        Console.Write("]");
    }
 
  // Driver code
  static void Main()
  {
     
    // Given array
    int[] arr = { 3, 1, 3, 2 };
  
    // Stores the length of array
    int N = arr.Length;
  
    // Given value of K
    int K = 4;
  
    // Function call
    findElementPositions(arr, N, K);
  }
}
 
// This code is contributed by rameshtravel07

Javascript

<script>
    // Javascript program for the above approach
     
    // Function to print position of array
    // elements after performing given
    // operations exactly K times
    function findElementPositions(arr, N, K)
    {
 
        // make the queue of pairs
        let que = [];
 
        // Convert the array
        // to queue of pairs
        for (let i = 0; i < N; i++) {
            que.push([ arr[i], i ]);
        }
 
        // Perform the operations
        // for K units of time
        for (let i = 0; i < K; i++) {
 
            // get the front pair
            let value = que[0];
 
            // If the first element
            // value is one
            if (value[0] == 1) {
                que.shift();
            }
 
            // Otherwise
            else {
                que.shift();
                value[0] -= 1;
                que.push(value);
            }
        }
 
        // Print all the positions
        // after K operations
        document.write("[");
        while (que.length > 0) {
 
            let value = que[0];
            que.shift();
            if(que.length > 0)
            {
                document.write(value[1] + ", ");
            }
            else{
                document.write(value[1]);
            }
             
        }
        document.write("]");
    }
     
    // Given array
    let arr = [ 3, 1, 3, 2 ];
  
    // Stores the length of array
    let N = arr.length;
  
    // Given value of K
    let K = 4;
  
    // Function call
    findElementPositions(arr, N, K);
 
// This code is contributed by mukesh07.
</script>
Producción: 

[0, 2, 3]

 

Complejidad de tiempo: O(max(N, K))
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por rohitsingh07052 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *