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, el elemento que tiene la diferencia mínima aparece primero y así sucesivamente, utilizando un espacio extra constante.
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[] = {10, 5, 3, 9, 2}
x = 7
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 : arr[] = {1, 2, 3, 4, 5}
x = 6
Output : arr[] = {5, 4, 3, 2, 1}
El problema anterior ya se ha explicado en una publicación anterior aquí . Toma O(n log n) tiempo y O(n) espacio extra. Sin embargo, la siguiente solución tiene una complejidad de tiempo relativamente mala, es decir, O (n ^ 2), pero hace el trabajo sin usar espacio o memoria adicional.
La solución está basada en el tipo de inserción . Para cada i (1<= i < n) comparamos el valor absoluto de la diferencia de arr[i] con el número dado x (Sea esto ‘diff’). Luego comparamos esta diferencia con la diferencia de abs(arr[j]-x) donde 0<= j <i (Sea esto si abdiff). Si diff es mayor que abdiff, cambiamos los valores en la array para acomodar arr[i] en su posición correcta.
C++
// C++ program to sort an array based on absolute
// difference with a given value x.
#include <bits/stdc++.h>
using namespace std;
void arrange(int arr[], int n, int x)
{
// Below lines are similar to insertion sort
for (int i = 1; i < n; i++) {
int diff = abs(arr[i] - x);
// Insert arr[i] at correct place
int j = i - 1;
if (abs(arr[j] - x) > diff) {
int temp = arr[i];
while (abs(arr[j] - x) > diff && j >= 0) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
}
}
// Function to print the array
void print(int arr[], int n)
{
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}
// Main Function
int main()
{
int arr[] = { 10, 5, 3, 9, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 7;
arrange(arr, n, x);
print(arr, n);
return 0;
}
Java
// Java program to sort an array based on absolute
// difference with a given value x.
class GFG {
static void arrange(int arr[], int n, int x)
{
// Below lines are similar to insertion sort
for (int i = 1; i < n; i++) {
int diff = Math.abs(arr[i] - x);
// Insert arr[i] at correct place
int j = i - 1;
if (Math.abs(arr[j] - x) > diff)
{
int temp = arr[i];
while (j >= 0 && Math.abs(arr[j] - x) > diff)
{
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
}
}
// Function to print the array
static void print(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;
arrange(arr, n, x);
print(arr, n);
}
}
// This code is contributed by PrinciRaj1992
Python 3
# Python 3 program to sort an array # based on absolute difference with # a given value x. def arrange(arr, n, x): # Below lines are similar to # insertion sort for i in range(1, n) : diff = abs(arr[i] - x) # Insert arr[i] at correct place j = i - 1 if (abs(arr[j] - x) > diff) : temp = arr[i] while (abs(arr[j] - x) > diff and j >= 0) : arr[j + 1] = arr[j] j -= 1 arr[j + 1] = temp # Function to print the array def print_1(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 arrange(arr, n, x) print_1(arr, n) # This code is contributed by ita_c
C#
// C# program to sort an array based on absolute
// difference with a given value x.
using System;
class GFG
{
static void arrange(int []arr, int n, int x)
{
// Below lines are similar to insertion sort
for (int i = 1; i < n; i++)
{
int diff = Math.Abs(arr[i] - x);
// Insert arr[i] at correct place
int j = i - 1;
if (Math.Abs(arr[j] - x) > diff)
{
int temp = arr[i];
while (j >= 0 && Math.Abs(arr[j] - x) > diff)
{
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
}
}
// Function to print the array
static void print(int []arr, int n)
{
for (int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
}
// Driver code
public static void Main()
{
int []arr = { 10, 5, 3, 9, 2 };
int n = arr.Length;
int x = 7;
arrange(arr, n, x);
print(arr, n);
}
}
// This code is contributed by 29AjayKumar
PHP
<?php
// PHP program to sort an array based on
// absolute difference with a given value x.
function arrange($arr, $n, $x)
{
// Below lines are similar to
// insertion sort
for ($i = 1; $i < $n; $i++)
{
$diff = abs($arr[$i] - $x);
// Insert arr[i] at correct place
$j = $i - 1;
if (abs($arr[$j] - $x) > $diff)
{
$temp = $arr[$i];
while (abs($arr[$j] - $x) >
$diff && $j >= 0)
{
$arr[$j + 1] = $arr[$j];
$j--;
}
$arr[$j + 1] = $temp;
}
}
return $arr;
}
// Function to print the array
function print_arr($arr, $n)
{
for ($i = 0; $i < $n; $i++)
echo $arr[$i] . " ";
}
// Driver Code
$arr = array(10, 5, 3, 9, 2);
$n = sizeof($arr);
$x = 7;
$arr1 = arrange($arr, $n, $x);
print_arr($arr1, $n);
// This code is contributed
// by Akanksha Rai
?>
Javascript
<script>
// Javascript program to sort
// an array based on absolute
// difference with a given value x.
function arrange(arr,n,x)
{
// Below lines are similar
// to insertion sort
for (let i = 1; i < n; i++) {
let diff = Math.abs(arr[i] - x);
// Insert arr[i] at correct place
let j = i - 1;
if (Math.abs(arr[j] - x) > diff)
{
let temp = arr[i];
while (j >= 0 &&
Math.abs(arr[j] - x) > diff)
{
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
}
}
// Function to print the array
function print(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;
arrange(arr, n, x);
print(arr, n);
// This code is contributed
// by avanitrachhadiya2155
</script>
Producción:
5 9 10 3 2
Complejidad de tiempo: O(n^2) donde n es el tamaño de la array.
Espacio auxiliar: O(1)
Este artículo es una contribución de Rohit Rao . 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 contribuido@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