Reemplace cada elemento de Array con su rango correspondiente

Posted on by Rudeus Greyrat

Dada una array arr[] de N enteros, la tarea es reemplazar cada elemento de la array con su rango en la array .

El rango de un elemento se define como la distancia entre el elemento y el primer elemento de la array cuando la array se organiza en orden ascendente. Si dos o más son iguales en la array, su rango también es el mismo que el rango de la primera aparición del elemento. 
Por ejemplo: Sea la array dada arr[] = {2, 2, 1, 6}, luego el rango de los elementos viene dado por: la 
array ordenada es: 
arr[] = {1, 2, 2, 6} 
Rank(1) = 1 (en el índice 0) 
Rango (2) = 2 (en el índice 1) 
Rango (2) = 2 (en el índice 2) 
Rango (6) = 4 (en el índice 3)

Ejemplos:

Entrada: arr[] = [100, 5, 70, 2] 
Salida: [4, 2, 3, 1] 
Explicación: 
El rango de 2 es 1, 5 es 2, 70 es 3 y 100 es 4.
Entrada: arr[ ] = [100, 2, 70, 2] 
Salida: [3, 1, 2, 1] 
Explicación: 
el rango de 2 es 1, 70 es 2 y 100 es 3.

Enfoque ingenuo: el enfoque ingenuo consiste en encontrar que el rango de cada elemento es 1 + el recuento de elementos más pequeños en la array para el elemento actual.
Complejidad de tiempo: O(N 2 ) 
Espacio auxiliar: O(1)
Enfoque eficiente: Para optimizar el enfoque ingenuo anterior, busque rangos de elementos y luego asigne el rango a los elementos. A continuación se muestran los pasos:

  1. Para calcular el rango del elemento, primero haga una copia de arr[] dado y luego ordene esa array copiada en orden ascendente.
  2. Luego recorra la array copiada y coloque su rango en HashMap tomando una variable de rango.
  3. Si el elemento ya está presente en HashMap, no actualice el rango; de lo contrario, actualice el rango del elemento en HashMap e incremente también la variable de rango.
  4. Atraviese la array dada arr[] asigne el rango de cada elemento usando el rango almacenado en HashMap.

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 assign rank to
// array elements
void changeArr(int input[], int N)
{
     
    // Copy input array into newArray
    int newArray[N];
    copy(input, input + N, newArray);
 
    // Sort newArray[] in ascending order
    sort(newArray, newArray + N);
    int i;
     
    // Map to store the rank of
    // the array element
    map<int, int> ranks;
 
    int rank = 1;
 
    for(int index = 0; index < N; index++)
    {
 
        int element = newArray[index];
 
        // Update rank of element
        if (ranks[element] == 0)
        {
            ranks[element] = rank;
            rank++;
        }
    }
 
    // Assign ranks to elements
    for(int index = 0; index < N; index++)
    {
        int element = input[index];
        input[index] = ranks[input[index]];
    }
}
 
// Driver code   
int main()
{
     
    // Given array arr[]
    int arr[] = { 100, 2, 70, 2 };
 
    int N = sizeof(arr) / sizeof(arr[0]);
     
    // Function call
    changeArr(arr, N);
 
    // Print the array elements
    cout << "[";
    for(int i = 0; i < N - 1; i++)
    {
        cout << arr[i] << ", ";
    }
    cout << arr[N - 1] << "]";
    return 0;
}
 
// This code is contributed by divyeshrabadiya07

Java

// Java program for the above approach
import java.util.*;
 
class GFG {
 
    // Function to assign rank to
    // array elements
    static void changeArr(int[] input)
    {
        // Copy input array into newArray
        int newArray[]
            = Arrays
                .copyOfRange(input,
                            0,
                            input.length);
 
        // Sort newArray[] in ascending order
        Arrays.sort(newArray);
        int i;
         
        // Map to store the rank of
        // the array element
        Map<Integer, Integer> ranks
            = new HashMap<>();
 
        int rank = 1;
 
        for (int index = 0;
            index < newArray.length;
            index++) {
 
            int element = newArray[index];
 
            // Update rank of element
            if (ranks.get(element) == null) {
 
                ranks.put(element, rank);
                rank++;
            }
        }
 
        // Assign ranks to elements
        for (int index = 0;
            index < input.length;
            index++) {
 
            int element = input[index];
            input[index]
                = ranks.get(input[index]);
         
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Given array arr[]
        int[] arr = { 100, 2, 70, 2 };
 
        // Function Call
        changeArr(arr);
 
        // Print the array elements
        System
            .out
            .println(Arrays
                        .toString(arr));
    }
}

Python3

# Python3 program for the above approach
 
# Function to assign rank to
# array elements
def changeArr(input1):
 
    # Copy input array into newArray
    newArray = input1.copy()
     
    # Sort newArray[] in ascending order
    newArray.sort()
     
    # Dictionary to store the rank of
    # the array element
    ranks = {}
     
    rank = 1
     
    for index in range(len(newArray)):
        element = newArray[index];
     
        # Update rank of element
        if element not in ranks:
            ranks[element] = rank
            rank += 1
         
    # Assign ranks to elements
    for index in range(len(input1)):
        element = input1[index]
        input1[index] = ranks[input1[index]]
 
# Driver Code
if __name__ == "__main__":
     
    # Given array arr[]
    arr = [ 100, 2, 70, 2 ]
     
    # Function call
    changeArr(arr)
     
    # Print the array elements
    print(arr)
 
# This code is contributed by chitranayal

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
using System.Text;
 
class GFG{
 
// Function to assign rank to
// array elements
static void changeArr(int[] input)
{
     
    // Copy input array into newArray
    int []newArray = new int[input.Length];
    Array.Copy(input, newArray, input.Length);
 
    // Sort newArray[] in ascending order
    Array.Sort(newArray);
     
    // To store the rank of
    // the array element
    Dictionary<int,
            int> ranks= new Dictionary<int,
                                        int>();
 
    int rank = 1;
 
    for(int index = 0;
            index < newArray.Length;
            index++)
    {
        int element = newArray[index];
 
        // Update rank of element
        if (!ranks.ContainsKey(element))
        {
            ranks[element] = rank;
            rank++;
        }
    }
 
    // Assign ranks to elements
    for(int index = 0;
            index < input.Length;
            index++)
    {
        input[index] = ranks[input[index]];
    }
}
 
// Driver Code
public static void Main(string[] args)
{
     
    // Given array arr[]
    int[] arr = { 100, 2, 70, 2 };
 
    // Function call
    changeArr(arr);
 
    // Print the array elements
    Console.WriteLine("[{0}]",
        string.Join(", ", arr));
}
}
 
// This code is contributed by rutvik_56

Javascript

<script>
 
// Javascript program for the above approach
 
// Function to assign rank to
// array elements
function changeArr(input, N)
{
     
    // Copy input array into newArray
    var newArray = JSON.parse(JSON.stringify(input));
 
    // Sort newArray[] in ascending order
    newArray.sort((a,b)=> a-b);
 
    var i;
     
    // Map to store the rank of
    // the array element
    var ranks = new Map();
 
    var rank = 1;
 
    for(var index = 0; index < N; index++)
    {
 
        var element = newArray[index];
 
        // Update rank of element
        if (!ranks.has(element))
        {
            ranks.set(element, rank);
            rank++;
        }
    }
 
    // Assign ranks to elements
    for(var index = 0; index < N; index++)
    {
        var element = input[index];
        input[index] = ranks.get(input[index]);
    }
    return input;
}
 
// Driver code 
 
// Given array arr[]
var arr = [100, 2, 70, 2];
var N = arr.length;
 
// Function call
arr = changeArr(arr, N);
 
// Print the array elements
document.write( "[");
for(var i = 0; i < N - 1; i++)
{
    document.write( arr[i] + ", ");
}
document.write( arr[N - 1] + "]");
 
// This code is contributed by famously.
</script>

[3, 1, 2, 1]

Complejidad de tiempo: O(N * log N)  
Espacio auxiliar: O(N)
 

Publicación traducida automáticamente

Artículo escrito por offbeat 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 *