Encuentre el orden ordenado de Array después de reemplazar los dígitos con su alternativa dada

Dada una array A[] que contiene N enteros y otra array M[] que contiene valores alternativos de todos los dígitos del 0 al 9 (es decir, M[i] = j significa que j es un valor alternativo de i ( 0 ≤ i, j ≤ 9)), Realice las siguientes operaciones en la array:

• Reemplace todos los dígitos de todos los elementos de la array A[] con sus alternativas dadas en M[] .
• Ordene la array según el nuevo valor de los elementos.
• Devuelve los valores anteriores en el orden ordenado de los valores nuevos (es decir, reemplaza los valores nuevos con sus valores anteriores). 

La tarea es encontrar este orden ordenado final de elementos.

Nota: Los elementos que tienen el mismo valor nuevo deben ordenarse según su posición en la array original A[] .

Ejemplos:

Entrada: N = 3, A = {991, 338, 38}, M = {8, 9, 4, 0, 2, 1, 3, 5, 7, 6}
Salida: {338, 38, 991}
Explicación: Cálculo del nuevo valor de 991: M[9] = 6, M[9] = 6, M[1] = 9. Entonces 991 => 669
El nuevo valor de 338 es 007, es decir, igual a 7.
El nuevo valor de 38 es 07 o 7. 
Entonces, la array ordenada de nuevos valores es {7, 7, 669}.
Entonces el orden ordenado es {338, 38, 991}. 
Debido a que tanto 338 como 38 tienen el mismo valor, 7 y 338 vienen antes que 38 en la array real.

Entrada: N = 5, A[] = {20, 25, 10, 5, 77}, M = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Salida: {5, 10, 20, 25, 77}

Enfoque: La idea a resolver es según lo siguiente:

En primer lugar, reemplace los dígitos con sus suplentes y luego ordene el valor recién formado en orden creciente. Luego organice la array original de acuerdo con el orden ordenado de los elementos recién formados.

Siga los pasos para resolver el problema:

• Haz un vector de pares (digamos v ).
• Iterar la array de i = 0 a N-1 :
  • Reemplace todos los dígitos de los elementos con sus suplentes de M[] y busque el nuevo valor (digamos temp ).
  • Haz un par que tenga temp como primer elemento y A[i] como segundo elemento.
  • Empuje el par en v .
• Ordene el vector v en orden creciente de los primeros valores de los pares (es decir, los valores recién formados después de reemplazar los dígitos con suplentes).
• Ahora organice la array de manera que A[i] sea el mismo que el segundo valor de v[i].

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 new value of an
// integer by mapping digits from M
int newValue(int num, int M[])
{
    string s = to_string(num);
    int New_Value = 0, x = 0;
    for (int i = s.size() - 1; i >= 0; i--) {
        New_Value += (M[s[i] - 0]
                      * pow(10, x));
        x++;
    }
    return New_Value;
}
 
// Comparator function for sorting
bool comp(pair<int, int>& p1,
          pair<int, int>& p2)
{
    return p1.first < p2.first;
}
 
// Function to Sort the given array
// according to the New Value of digits
void sortArray(int N, int A[], int M[])
{
    // Vector to store pair of elements
    // and their new values
    vector<pair<int, int> > v;
 
    // Pushing pairs of New value of elements
    // and elements into vector v
    for (int i = 0; i < N; i++) {
        int New_Value = newValue(A[i], M);
        v.push_back({ New_Value, A[i] });
    }
 
    // Sorting the vector "v" in
    // increasing order of first
    // element of pair
    sort(v.begin(), v.end(), comp);
 
    // Storing the values of second value
    // of vector "v" in array "A"
    for (int i = 0; i < N; i++) {
        A[i] = v[i].second;
    }
    for (int i = 0; i < N; i++) {
        cout << A[i] << " ";
    }
}
 
// Driver Code
int main()
{
    int N = 3;
    int A[] = { 991, 338, 38 };
    int M[] = { 8, 9, 4, 0, 2, 1, 3, 5, 7, 6 };
 
    // Function call
    sortArray(N, A, M);
    return 0;
}

import java.util.*;
import java.io.*;
 
// Java program for the above approach
class GFG{
 
  // Function to find new value of an
  // integer by mapping digits from M
  public static int newValue(int num, int M[])
  {
    String s = Integer.toString(num);
    int New_Value = 0;
    int x = 0;
    for (int i = s.length() - 1; i >= 0; i--) {
      New_Value += (M[s.charAt(i) - '0'] * Math.pow(10, x));
      x++;
    }
    return New_Value;
  }
 
  // Function to Sort the given array
  // according to the New Value of digits
  public static void sortArray(int N, int A[], int M[])
  {
    // Vector to store pair of elements
    // and their new values
    ArrayList<pair> v = new ArrayList<pair>();
 
    // Pushing pairs of New value of elements
    // and elements into vector v
    for (int i = 0; i < N; i++) {
      int New_Value = newValue(A[i], M);
      v.add(new pair(New_Value, A[i]));
    }
 
    // Sorting the vector "v" in
    // increasing order of first
    // element of pair
    Collections.sort(v, new comp());
 
    // Storing the values of second value
    // of vector "v" in array "A"
    for (int i = 0; i < N; i++) {
      A[i] = v.get(i).y;
    }
    for (int i = 0; i < N; i++) {
      System.out.print(A[i] + " ");
    }
  }
 
  // Driver code
  public static void main(String args[])
  {
    int N = 3;
    int A[] = {991, 338, 38};
    int M[] = {8, 9, 4, 0, 2, 1, 3, 5, 7, 6};
 
    // Function call
    sortArray(N, A, M);
  }
}
 
// Custom pair class
class pair{
  Integer x;
  Integer y;
  pair(int x,int y){
    this.x = x;
    this.y = y;
  }
}
 
// Comparator for pair class
class comp implements Comparator<pair>{
  public int compare(pair o1, pair o2){
    return o1.x.compareTo(o2.x);
  }
}
 
// This code is contributed by subhamgoyal2014.

# Python code for the above approach
 
# Function to find new value of an
# integer by mapping digits from M
from functools import cmp_to_key
import math
 
def mycmp(a,b):
    return a[0] - b[0]
 
def newValue(num, M):
    s = str(num)
    New_Value,x = 0,0
    for i in range(len(s) - 1,-1,-1):
        New_Value += (M[ord(s[i]) - ord('0')]* math.pow(10, x))
        x += 1
    return New_Value
 
# Function to Sort the given array
# according to the New Value of digits
def sortArray(N, A, M):
 
    # Vector to store pair of elements
    # and their new values
    v = []
 
    # Pushing pairs of New value of elements
    # and elements into vector v
    for i in range(N):
        New_Value = newValue(A[i], M)
        v.append([New_Value,A[i]])
 
    # Sorting the vector "v" in
    # increasing order of first
    # element of pair
    v.sort(key = cmp_to_key(mycmp))
 
    # Storing the values of second value
    # of vector "v" in array "A"
    for i in range(N):
        A[i] = v[i][1]
 
    for i in range(N):
        print(A[i],end = " ")
 
# Driver Code
N = 3
A = [991, 338, 38]
M = [8, 9, 4, 0, 2, 1, 3, 5, 7, 6]
 
# Function call
sortArray(N, A, M)
 
# This code is contributed by shinjanpatra

<script>
    // JavaScript code for the above approach
 
    // Function to find new value of an
    // integer by mapping digits from M
    function newValue(num, M) {
        let s = (num).toString();
        let New_Value = 0, x = 0;
        for (let i = s.length - 1; i >= 0; i--) {
            New_Value += (M[s[i] - 0]
                * Math.pow(10, x));
            x++;
        }
        return New_Value;
    }
 
 
    // Function to Sort the given array
    // according to the New Value of digits
    function sortArray(N, A, M)
    {
     
        // Vector to store pair of elements
        // and their new values
        let v = [];
 
        // Pushing pairs of New value of elements
        // and elements into vector v
        for (let i = 0; i < N; i++) {
            let New_Value = newValue(A[i], M);
            v.push({ first: New_Value, second: A[i] });
        }
 
        // Sorting the vector "v" in
        // increasing order of first
        // element of pair
        v.sort(function (a, b) { return a.first - b.first })
 
        // Storing the values of second value
        // of vector "v" in array "A"
        for (let i = 0; i < N; i++) {
            A[i] = v[i].second;
        }
        for (let i = 0; i < N; i++) {
            document.write(A[i] + " ");
        }
    }
 
    // Driver Code
    let N = 3;
    let A = [991, 338, 38];
    let M = [8, 9, 4, 0, 2, 1, 3, 5, 7, 6];
 
    // Function call
    sortArray(N, A, M);
 
    // This code is contributed by Potta Lokesh
</script>

338 38 991 

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