Dada una array de n elementos distintos y un número x, organice los elementos de la array de acuerdo con la diferencia absoluta con x, es decir, un elemento que tenga una diferencia mínima aparece primero, y así sucesivamente.
Nota: si dos o más elementos están a la misma distancia, organícelos en la misma secuencia que en la array dada.
Ejemplos:
Input : arr[] : x = 7, arr[] = {10, 5, 3, 9, 2}
Output : arr[] = {5, 9, 10, 3, 2}
Explanation:
7 - 10 = 3(abs)
7 - 5 = 2
7 - 3 = 4
7 - 9 = 2(abs)
7 - 2 = 5
So according to the difference with X,
elements are arranged as 5, 9, 10, 3, 2.
Input : x = 6, arr[] = {1, 2, 3, 4, 5}
Output : arr[] = {5, 4, 3, 2, 1}
Input : x = 5, arr[] = {2, 6, 8, 3}
Output : arr[] = {6, 3, 2, 8}
La idea es utilizar un árbol de búsqueda binario autoequilibrado. Atravesamos la array de entrada y para cada elemento, encontramos su diferencia con x y almacenamos la diferencia como clave y el elemento como el valor en un árbol de búsqueda binario autoequilibrado. Finalmente, recorremos el árbol e imprimimos su recorrido en orden, que es la salida requerida.
Implementación de C++:
en C++, el árbol de búsqueda binaria de autoequilibrio se implementa mediante set , map y multimap . No podemos usar set aquí ya que tenemos pares clave-valor (no solo claves). Tampoco podemos usar el mapa directamente, ya que una sola clave puede pertenecer a múltiples valores y el mapa permite un solo valor para una clave. Entonces usamos multimapa que almacena pares clave-valor y puede tener múltiples valores para una clave.
- Almacene los valores en el mapa múltiple con la diferencia con X como clave.
- En multimapa, los valores ya estarán ordenados según la clave, es decir, la diferencia con X porque implementa el árbol de búsqueda binaria de autoequilibrio internamente.
- Actualice todos los valores de una array con los valores del mapa para que la array tenga la salida requerida.
C++
// C++ program to sort an array according absolute
// difference with x.
#include<bits/stdc++.h>
using namespace std;
// Function to sort an array according absolute
// difference with x.
void rearrange(int arr[], int n, int x)
{
multimap<int, int> m;
multimap<int ,int >:: iterator it;
// Store values in a map with the difference
// with X as key
for (int i = 0 ; i < n; i++)
m.insert(make_pair(abs(x-arr[i]),arr[i]));
// Update the values of array
int i = 0;
for (it = m.begin(); it != m.end(); it++)
arr[i++] = (*it).second ;
}
// Function to print the array
void printArray(int arr[] , int n)
{
for (int i = 0 ; i < n; i++)
cout << arr[i] << " ";
}
// Driver code
int main()
{
int arr[] = {10, 5, 3, 9 ,2};
int n = sizeof(arr)/sizeof(arr[0]);
int x = 7;
rearrange(arr, n, x);
printArray(arr, n);
return 0;
}
Java
// Java program to sort an array according absolute
// difference with x.
import java.io.*;
import java.util.*;
class GFG
{
// Function to sort an array according absolute
// difference with x.
static void rearrange(int[] arr, int n, int x)
{
TreeMap<Integer, ArrayList<Integer>> m =
new TreeMap<>();
// Store values in a map with the difference
// with X as key
for (int i = 0; i < n; i++)
{
int diff = Math.abs(x - arr[i]);
if (m.containsKey(diff))
{
ArrayList<Integer> al = m.get(diff);
al.add(arr[i]);
m.put(diff, al);
}
else
{
ArrayList<Integer> al = new
ArrayList<>();
al.add(arr[i]);
m.put(diff,al);
}
}
// Update the values of array
int index = 0;
for (Map.Entry entry : m.entrySet())
{
ArrayList<Integer> al = m.get(entry.getKey());
for (int i = 0; i < al.size(); i++)
arr[index++] = al.get(i);
}
}
// Function to print the array
static void printArray(int[] arr, int n)
{
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
// Driver code
public static void main(String args[])
{
int[] arr = {10, 5, 3, 9 ,2};
int n = arr.length;
int x = 7;
rearrange(arr, n, x);
printArray(arr, n);
}
}
// This code is contributed by rachana soma
Python3
# Python3 program to sort an
# array according absolute
# difference with x.
# Function to sort an array
# according absolute difference
# with x.
def rearrange(arr, n, x):
m = {}
# Store values in a map
# with the difference
# with X as key
for i in range(n):
m[arr[i]] = abs(x - arr[i])
m = {k : v for k, v in sorted(m.items(),
key = lambda item : item[1])}
# Update the values of array
i = 0
for it in m.keys():
arr[i] = it
i += 1
# Function to print the array
def printArray(arr, n):
for i in range(n):
print(arr[i], end = " ")
# Driver code
if __name__ == "__main__":
arr = [10, 5, 3, 9, 2]
n = len(arr)
x = 7
rearrange(arr, n, x)
printArray(arr, n)
# This code is contributed by Chitranayal
C#
// C# program to sort an array according absolute
// difference with x.
using System;
using System.Collections.Generic;
public class GFG
{
// Function to sort an array according absolute
// difference with x.
static void rearrange(int[] arr, int n, int x)
{
SortedDictionary<int,List<int>> m = new SortedDictionary<int,List<int>>();
// Store values in a map with the difference
// with X as key
for (int i = 0; i < n; i++)
{
int diff = Math.Abs(x - arr[i]);
if (m.ContainsKey(diff))
{
List<int> al = m;
al.Add(arr[i]);
m = al;
}
else
{
List<int> al = new List<int>();
al.Add(arr[i]);
m.Add(diff, al);
}
}
// Update the values of array
int index = 0;
foreach(int entry in m.Keys)
{
List<int> al = m[entry];
for (int i = 0; i < al.Count; i++)
arr[index++] = al[i];
}
}
// Function to print the array
static void printArray(int[] arr, int n)
{
for (int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
}
// Driver code
static public void Main (){
int[] arr = {10, 5, 3, 9 ,2};
int n = arr.Length;
int x = 7;
rearrange(arr, n, x);
printArray(arr, n);
}
}
// This code is contributed by avanitrachhadiya2155
Javascript
<script>
// JavaScript program to sort an array according absolute
// difference with x.
// Function to sort an array according absolute
// difference with x.
function rearrange(arr,n,x)
{
let m = new Map();
// Store values in a map with the difference
// with X as key
for (let i = 0; i < n; i++)
{
m.set(arr[i],Math.abs(x-arr[i]));
}
let m1 = new Map([...m.entries()].sort((a, b) =>
a[1] - b[1]));
// Update the values of array
let index = 0;
for (let [key, value] of m1.entries())
{
arr[index++] =key
}
}
// Function to print the array
function printArray(arr,n)
{
for (let i = 0; i < n; i++)
document.write(arr[i] + " ");
}
// Driver code
let arr=[10, 5, 3, 9 ,2];
let n = arr.length;
let x = 7;
rearrange(arr, n, x);
printArray(arr, n);
// This code is contributed by ab2127
</script>
5 9 10 3 2
Complejidad de tiempo: O(n Log n)
Espacio auxiliar: O(n)
Este artículo es una contribución de Sahil Chhabra . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Implementación basada en C++ STL : en C++, podemos usar stable_sort() y escribir una expresión lambda para la función de comparación personalizada. Esta solución es elegante y mucho más fácil de entender. El único desafío al escribir la expresión lambda es enviar el valor ‘x’ a la expresión lambda para poder usarlo dentro de la expresión. Esto se puede lograr mediante la sobrecarga de operadores con la ayuda de una clase o utilizando una captura mucho más simple.
C++
// CPP program for the above approach
#include <bits/stdc++.h>
using namespace std;
void rearrange(int arr[], int n, int x)
{
/*
We can send the value x into
lambda expression as
follows: [capture]()
{
//statements
//capture value can be used inside
}
*/
stable_sort(arr, arr + n, [x](int a, int b)
{
if (abs(a - x) < abs(b - x))
return true;
else
return false;
});
}
// Driver code
int main()
{
int arr[] = { 10, 5, 3, 9, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 7;
rearrange(arr, n, x);
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
5 9 10 3 2
Complejidad de tiempo : dado que estamos usando un tipo estable de STL, que usa una variación de ordenación por fusión, la complejidad de tiempo es O (n logn).
Este artículo es una contribución de D. Mohit Varsha. Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA