Python | Ordenar una array según la diferencia absoluta

Dada una array de N elementos distintos y un número val , reorganiza los elementos de la array de acuerdo con la diferencia absoluta con val , es decir, el elemento que tiene la diferencia mínima aparece primero y así sucesivamente. Además, el orden de los elementos de la array debe mantenerse en caso de que dos o más elementos tengan diferencias iguales.

Ejemplos:

Entrada: val = 6, a = [7, 12, 2, 4, 8, 0]
Salida: a = [7 4 8 2 12 0]

Explicación:
Considere la diferencia absoluta de cada elemento del arreglo y ‘val’
7 – 6 = 1
12- 6 = 6
2 – 6 = 4 (abs)
4 – 6 = 2 (abs)
8 – 6 = 2
0 – 6 = 6 (abs)
Entonces, de acuerdo con las diferencias obtenidas, ordene las diferencias de array en orden creciente,
se obtiene 1, 2, 2, 4, 6, 6, y sus elementos de array correspondientes son 7, 4, 8, 2, 12, 0 .

Entrada: val = -2, a = [5, 2, 0, -4]
Salida: a = [0 -4 2 5]

Enfoque: normalmente, un diccionario en Python puede contener solo un valor correspondiente a una clave. Pero en este problema es posible que tengamos que almacenar múltiples valores para una clave en particular. Claramente, no se puede usar un diccionario simple, necesitamos algo como un mapa múltiple en C++ . Entonces, aquí se usa el diccionario predeterminado, que funciona como Multimap en Python. Los siguientes son los pasos para resolver el problema.

• Almacene los valores en el diccionario, donde la clave es la diferencia absoluta entre ‘val’ y los elementos de la array (es decir, abs (val-a[i])) y el valor son los elementos de la array (es decir, a[i])
• En multiimap, los valores ya estarán ordenados según la clave porque implementa el árbol de búsqueda binaria de autoequilibrio internamente.
• Actualice los valores de la array original almacenando los elementos del diccionario uno por uno.

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

# Python program to sort the array
# according to a value val 
  
# Using Default dictionary (works as Multimap in Python)
from collections import defaultdict
def rearrange(a, n, val):
     # initialize Default dictionary
     dict = defaultdict(list)  
       
     # Store values in dictionary (i.e. multimap) where,
     # key: absolute difference between 'val' 
     # and array elements (i.e. abs(val-a[i])) and
     # value: array elements (i.e. a[i])
     for i in range(0, n):
          dict[abs(val-a[i])].append(a[i])
       
     index = 0  
       
     # Update the values of original array 
     # by storing the dictionary elements one by one
     for i in dict:
           
          pos = 0
          while (pos<len(dict[i])):
               a[index]= dict[i][pos]
               index+= 1
               pos+= 1
       
# Driver code     
a =[7, 12, 2, 4, 8, 0]
val = 6
  
# len(a) gives the length of the list
rearrange(a, len(a), val)
  
# print the modified final list
for i in a:
     print(i, end =' ')  

7 4 8 2 12 0

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

Enfoque alternativo: use una array 2-D de tamaño n*2 para almacenar la diferencia absoluta y el índice en (i, 0) y (i, 1). Ordenar la array 2-D. De acuerdo con la propiedad de array incorporada, la array se ordena en términos del primer elemento y, si el primer elemento es el mismo, se ordena según el segundo elemento. Obtenga el índice e imprima el elemento de array en consecuencia.

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

def printsorted(a, n, val):
      
    # declare a 2-D matrix 
    b =[[0 for x in range(2)] for y in range(n)]
      
    for i in range(0, n): 
        b[i][0] = abs(a[i]-val) 
        b[i][1] = i
          
      
    b.sort() 
      
    for i in range(0, n): 
        print a[b[i][1]],
      
          
      
a = [7, 12, 2, 4, 8, 0]
n = len(a) 
val = 6
printsorted(a, n, val) 

7 4 8 2 12 0

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