Encuentre la array ordenada después de elevar todos los elementos de la array a la potencia de K

Dada una array de enteros arr[] de tamaño N que está ordenada en orden creciente y un entero K , devuelve una array con potencia de K de cada número ordenado en orden creciente.

Ejemplos:

Entrada: arr[]: {-4, -1, 0, 3, 10}, K = 4
Salida:  {0, 1, 81, 256, 10000}
Explicación: Después de hacer la operación de potencia de 4,  
la array de elementos se convertirá en {256, 1, 0, 81, 10000},  
después de ordenar, la array se convertirá en {0, 1, 81, 256, 10000}.

Entrada: arr[]: {-7, -3, 2, 3, 11}, K = 4
Salida:  {16, 81, 81, 2401, 14641}

Enfoque ingenuo: la idea básica es:

En primer lugar, realice la operación de potencia de K en todos los elementos de la array y ordene la array utilizando la función de clasificación.

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

// C++ Code for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the array
// after performing the operation
vector<int> sortedpower(vector<int>& nums, int K)
{
    // Loop is used for perforimg power of K
    for (int i = 0; i < nums.size(); i++) {
        nums[i] = pow(nums[i], K);
    }
 
    // C++ STL function to sort the array
    // One can use different sorting algorithms
    sort(nums.begin(), nums.end());
 
    // Returning the vector which is the required answer
    return nums;
}
 
// Driver Code
int main()
{
    // Defining the vector v
    vector<int> arr = { -4, -1, 0, 3, 10 };
 
    // Function Call
    int K = 4;
    arr = sortedpower(arr, K);
    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

// Java Code for the above approach
import java.io.*;
import java.util.*;
 
class GFG {
    // Function to find the array
    // after performing the operation
    public static int[] sortedpower(int nums[], int K)
    {
        // Loop is used for perforimg power of K
        for (int i = 0; i < nums.length; i++) {
            nums[i] = (int)Math.pow(nums[i], K);
        }
 
        // Java library function to sort the array
        // One can use different sorting algorithms
        Arrays.sort(nums);
 
        // Returning the array which is the required answer
        return nums;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Defining the array v
        int arr[] = { -4, -1, 0, 3, 10 };
 
        // Function Call
        int K = 4;
        arr = sortedpower(arr, K);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}
 
// This code is contributed by Rohit Pradhan

<script>
// Function to find the array
// after performing the operation
function compare(a, b)
{
    return a - b;
}
 
function sortedpower(nums, K)
{
 
    // Loop is used for perforimg power of K
    for (let i = 0; i < nums.length; i++)
    {
        nums[i] = Math.pow(nums[i], K);
    }
 
    
    // One can use different sorting algorithms
    nums.sort();
 
    // Returning the vector which is the required answer
    return nums;
}
 
// Driver Code
 
    // Defining the vector v
   var arr = [ -4, -1, 0, 3, 10 ];
 
    // Function Call
    let K = 4;
    arr = sortedpower(arr, K);
    for (let i = 0; i < arr.length; i++) {
        document.write(arr[i]+ " ");
    }
   document.write( "<br>");
    
   // This code is contributed by satwik4409.
    </script>

0 1 81 256 10000 

Complejidad de tiempo: O(N * logN * logK) 
Espacio auxiliar: O(1) 

Enfoque eficiente:

Encuentre el elemento en arr[] mayor que igual a 0, digamos en el índice i y use dos punteros para iterar de i-1 a 0 e i a N-1, compare estos elementos simultáneamente y almacénelos en orden creciente de magnitud (valor absoluto) . 

Siga los pasos a continuación para implementar el enfoque anterior:

• En primer lugar, encuentre el elemento que es mayor o igual que 0.
• Si K es impar, simplemente realizaremos la operación potencia de K porque la array ya está ordenada y el signo de enteros después de realizar la operación Pow no cambiará.
• Si K es par,
  • Entonces habrá 2 casos.
    • Caso 1 : no hay ningún elemento mayor o igual que 0, es decir, la array solo tiene números negativos, luego almacene todos los elementos de la array en orden inverso en una nueva array.
    • Caso 2 : si existen elementos que son simplemente mayores o iguales a 0
      • Inicializar dos punteros. 
      • Primero recorra la array desde ese índice hasta el elemento final.
      • Segunda array poligonal desde ese índice hasta el primer elemento.
      • Mientras atraviesa, verifique los valores absolutos de ambos elementos simultáneamente y almacene la array en orden creciente de valores absolutos.
• Después de obtener la nueva array, realice la operación de potencia de K en todos los elementos de la nueva array, que es la respuesta requerida.

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

// C++ Code for above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the new array
vector<int> sortedpower(vector<int>& nums, int K)
{
    // Declaring new vector to store ans
    vector<int> v;
    if (K % 2 == 0) {
        int idx = -1;
 
        // Loop to find element which is just grater than or
        // equal to 0
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] >= 0) {
                idx = i;
                break;
            }
        }
 
        // If there is no element
        // which is greater than or equal to 0
        if (idx == -1) {
            for (int i = nums.size() - 1; i >= 0; i--) {
                v.push_back(nums[i]);
            }
        }
 
        // If we find that element
        else {
 
            // Making 2 pointers
            int i = idx - 1;
            int j = idx;
            while ((i >= 0) || (j < nums.size())) {
 
                // If there no negative number left in the
                // array
                if (i == -1) {
                    v.push_back(nums[j]);
                    j++;
                }
 
                // If there no positive number left in the
                // array
                else if (j == nums.size()) {
                    v.push_back(nums[i]);
                    i--;
                }
 
                // Compairing absolute values of negative
                // and positive number and arranging them in
                // increasing order of absolute values
                else if ((abs(nums[i]) > nums[j])) {
                    v.push_back(nums[j]);
                    j++;
                }
                else {
                    v.push_back(nums[i]);
                    i--;
                }
            }
        }
    }
    else {
        v = nums;
    }
 
    // Performing power of 4 operation on all the array
    // elements
    for (int i = 0; i < v.size(); i++) {
        v[i] = pow(v[i], K);
    }
    // Returning the required answer
    return v;
}
 
// Driver Code
int main()
{
    // Defining the vector v
    vector<int> arr = { -4, -1, 0, 3, 10 };
    int K = 4;
 
    // Function Call
    arr = sortedpower(arr, K);
    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

0 1 81 256 10000 

Complejidad temporal: O(N)  
Complejidad espacial: O(N)

Otro enfoque eficiente: 

Use dos punteros a la izquierda y a la derecha apuntando hacia el primer y último índice de la array, luego mueva los punteros uno hacia el otro, es decir, de izquierda a derecha y de derecha a izquierda, compare simultáneamente la potencia N de los valores del índice señalado y almacene en orden creciente.

Siga los pasos a continuación para implementar la idea:

• Haga 2 punteros a la izquierda y a la derecha que apunten hacia el primero y el último elemento de la array, respectivamente.
• Luego calcule la potencia de K de ambos valores y compárelos entre sí.
  • Si el izquierdo es más grande, empújelo en el último vector de respuesta e incremente el puntero izquierdo .
  • Si el derecho es más grande, empújelo en el último de ans vector y disminuya el puntero derecho .

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

// C++ Code for above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the required array
vector<int> sortedpower(vector<int>& nums, int K)
{
 
    // Creating vector of same size as nums to store the ans
    vector<int> v(nums.size());
 
    // Make 2 pointer k and j
    int k = 0;
    int j = nums.size() - 1;
 
    // Travering the vector in reverse order
    for (int i = nums.size() - 1; i >= 0; i--) {
 
        // Squaring both the elements
        int a = pow(nums[k], K);
        int b = pow(nums[j], K);
        if (a >= b) {
            v[i] = a;
            k++;
        }
        else {
            v[i] = b;
            j--;
        }
    }
 
    // Returning the required answer
    return v;
}
 
// Driver Code
int main()
{
 
    // Defining the vector v
    vector<int> arr = { -4, -1, 0, 3, 10 };
 
    int K = 4;
    // Function Call
    arr = sortedpower(arr, K);
    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

<script>
// Javascript Code for the above approach
 
// Function to find the required array
function sortedpower(nums, K)
{
    // Creating vector of same size as nums to store the ans
     let v = new Array(nums.length);
 
    // Make 2 pointer k and j
    let k = 0;
    let j = nums.length - 1;
 
    // Travering the vector in reverse order
    for (let i = nums.length - 1; i >= 0; i--) {
 
        // Squaring both the elements
        let a = Math.pow(nums[k], K);
        let b = Math.pow(nums[j], K);
        if (a >= b) {
            v[i] = a;
            k++;
        }
        else {
            v[i] = b;
            j--;
        }
    }
 
    // Returning the required answer
    return v;
}
 
// Driver Code
 
    // Defining the vector v
   let arr = [ -4, -1, 0, 3, 10 ];
 
    // Function Call
    let K = 4;
    arr = sortedpower(arr, K);
    for (let i = 0; i < arr.length; i++) {
        document.write(arr[i]+ " ");
    }
   document.write( "<br>");
    
   // This code is contributed by satwik4409.
    </script>

0 1 81 256 10000 

Complejidad temporal: O(N)  
Complejidad espacial: O(N)