Dada una array ordenada arr[] y un valor X, encuentre los k elementos más cercanos a X en arr[].
Ejemplos:
Input: K = 4, X = 35
arr[] = {12, 16, 22, 30, 35, 39, 42,
45, 48, 50, 53, 55, 56}
Output: 30 39 42 45
Tenga en cuenta que si el elemento está presente en la array, entonces no debería estar en la salida, solo se requieren los otros elementos más cercanos.
En las siguientes soluciones, se supone que todos los elementos de la array son distintos.
Una solución simple es hacer una búsqueda lineal de k elementos más cercanos.
- Comience desde el primer elemento y busque el punto de cruce (el punto antes del cual los elementos son menores o iguales a X y después del cual los elementos son mayores). Este paso toma tiempo O(n).
- Una vez que encontramos el punto de cruce, podemos comparar elementos en ambos lados del punto de cruce para imprimir los elementos k más cercanos. Este paso lleva O(k) tiempo.
La complejidad temporal de la solución anterior es O(n).
Una Solución Optimizada es encontrar k elementos en O(Logn + k) tiempo. La idea es utilizar la búsqueda binaria para encontrar el punto de cruce. Una vez que encontramos el índice del punto de cruce, podemos imprimir los k elementos más cercanos en un tiempo O(k).
C++
#include<stdio.h>
/* Function to find the cross over point (the point before
which elements are smaller than or equal to x and after
which greater than x)*/
int findCrossOver(int arr[], int low, int high, int x)
{
// Base cases
if (arr[high] <= x) // x is greater than all
return high;
if (arr[low] > x) // x is smaller than all
return low;
// Find the middle point
int mid = (low + high)/2; /* low + (high - low)/2 */
/* If x is same as middle element, then return mid */
if (arr[mid] <= x && arr[mid+1] > x)
return mid;
/* If x is greater than arr[mid], then either arr[mid + 1]
is ceiling of x or ceiling lies in arr[mid+1...high] */
if(arr[mid] < x)
return findCrossOver(arr, mid+1, high, x);
return findCrossOver(arr, low, mid - 1, x);
}
// This function prints k closest elements to x in arr[].
// n is the number of elements in arr[]
void printKclosest(int arr[], int x, int k, int n)
{
// Find the crossover point
int l = findCrossOver(arr, 0, n-1, x);
int r = l+1; // Right index to search
int count = 0; // To keep track of count of elements already printed
// If x is present in arr[], then reduce left index
// Assumption: all elements in arr[] are distinct
if (arr[l] == x) l--;
// Compare elements on left and right of crossover
// point to find the k closest elements
while (l >= 0 && r < n && count < k)
{
if (x - arr[l] < arr[r] - x)
printf("%d ", arr[l--]);
else
printf("%d ", arr[r++]);
count++;
}
// If there are no more elements on right side, then
// print left elements
while (count < k && l >= 0)
printf("%d ", arr[l--]), count++;
// If there are no more elements on left side, then
// print right elements
while (count < k && r < n)
printf("%d ", arr[r++]), count++;
}
/* Driver program to check above functions */
int main()
{
int arr[] ={12, 16, 22, 30, 35, 39, 42,
45, 48, 50, 53, 55, 56};
int n = sizeof(arr)/sizeof(arr[0]);
int x = 35, k = 4;
printKclosest(arr, x, 4, n);
return 0;
}
Java
// Java program to find k closest elements to a given value
class KClosest
{
/* Function to find the cross over point (the point before
which elements are smaller than or equal to x and after
which greater than x)*/
int findCrossOver(int arr[], int low, int high, int x)
{
// Base cases
if (arr[high] <= x) // x is greater than all
return high;
if (arr[low] > x) // x is smaller than all
return low;
// Find the middle point
int mid = (low + high)/2; /* low + (high - low)/2 */
/* If x is same as middle element, then return mid */
if (arr[mid] <= x && arr[mid+1] > x)
return mid;
/* If x is greater than arr[mid], then either arr[mid + 1]
is ceiling of x or ceiling lies in arr[mid+1...high] */
if(arr[mid] < x)
return findCrossOver(arr, mid+1, high, x);
return findCrossOver(arr, low, mid - 1, x);
}
// This function prints k closest elements to x in arr[].
// n is the number of elements in arr[]
void printKclosest(int arr[], int x, int k, int n)
{
// Find the crossover point
int l = findCrossOver(arr, 0, n-1, x);
int r = l+1; // Right index to search
int count = 0; // To keep track of count of elements
// already printed
// If x is present in arr[], then reduce left index
// Assumption: all elements in arr[] are distinct
if (arr[l] == x) l--;
// Compare elements on left and right of crossover
// point to find the k closest elements
while (l >= 0 && r < n && count < k)
{
if (x - arr[l] < arr[r] - x)
System.out.print(arr[l--]+" ");
else
System.out.print(arr[r++]+" ");
count++;
}
// If there are no more elements on right side, then
// print left elements
while (count < k && l >= 0)
{
System.out.print(arr[l--]+" ");
count++;
}
// If there are no more elements on left side, then
// print right elements
while (count < k && r < n)
{
System.out.print(arr[r++]+" ");
count++;
}
}
/* Driver program to check above functions */
public static void main(String args[])
{
KClosest ob = new KClosest();
int arr[] = {12, 16, 22, 30, 35, 39, 42,
45, 48, 50, 53, 55, 56
};
int n = arr.length;
int x = 35, k = 4;
ob.printKclosest(arr, x, 4, n);
}
}
/* This code is contributed by Rajat Mishra */
Python3
# Function to find the cross over point # (the point before which elements are # smaller than or equal to x and after # which greater than x) def findCrossOver(arr, low, high, x) : # Base cases if (arr[high] <= x) : # x is greater than all return high if (arr[low] > x) : # x is smaller than all return low # Find the middle point mid = (low + high) // 2 # low + (high - low)// 2 # If x is same as middle element, # then return mid if (arr[mid] <= x and arr[mid + 1] > x) : return mid # If x is greater than arr[mid], then # either arr[mid + 1] is ceiling of x # or ceiling lies in arr[mid+1...high] if(arr[mid] < x) : return findCrossOver(arr, mid + 1, high, x) return findCrossOver(arr, low, mid - 1, x) # This function prints k closest elements to x # in arr[]. n is the number of elements in arr[] def printKclosest(arr, x, k, n) : # Find the crossover point l = findCrossOver(arr, 0, n - 1, x) r = l + 1 # Right index to search count = 0 # To keep track of count of # elements already printed # If x is present in arr[], then reduce # left index. Assumption: all elements # in arr[] are distinct if (arr[l] == x) : l -= 1 # Compare elements on left and right of crossover # point to find the k closest elements while (l >= 0 and r < n and count < k) : if (x - arr[l] < arr[r] - x) : print(arr[l], end = " ") l -= 1 else : print(arr[r], end = " ") r += 1 count += 1 # If there are no more elements on right # side, then print left elements while (count < k and l >= 0) : print(arr[l], end = " ") l -= 1 count += 1 # If there are no more elements on left # side, then print right elements while (count < k and r < n) : print(arr[r], end = " ") r += 1 count += 1 # Driver Code if __name__ == "__main__" : arr =[12, 16, 22, 30, 35, 39, 42, 45, 48, 50, 53, 55, 56] n = len(arr) x = 35 k = 4 printKclosest(arr, x, 4, n) # This code is contributed by Ryuga
C#
// C# program to find k closest elements to
// a given value
using System;
class GFG {
/* Function to find the cross over point
(the point before which elements are
smaller than or equal to x and after which
greater than x)*/
static int findCrossOver(int []arr, int low,
int high, int x)
{
// Base cases
// x is greater than all
if (arr[high] <= x)
return high;
// x is smaller than all
if (arr[low] > x)
return low;
// Find the middle point
/* low + (high - low)/2 */
int mid = (low + high)/2;
/* If x is same as middle element, then
return mid */
if (arr[mid] <= x && arr[mid+1] > x)
return mid;
/* If x is greater than arr[mid], then
either arr[mid + 1] is ceiling of x or
ceiling lies in arr[mid+1...high] */
if(arr[mid] < x)
return findCrossOver(arr, mid+1,
high, x);
return findCrossOver(arr, low, mid - 1, x);
}
// This function prints k closest elements
// to x in arr[]. n is the number of
// elements in arr[]
static void printKclosest(int []arr, int x,
int k, int n)
{
// Find the crossover point
int l = findCrossOver(arr, 0, n-1, x);
// Right index to search
int r = l + 1;
// To keep track of count of elements
int count = 0;
// If x is present in arr[], then reduce
// left index Assumption: all elements in
// arr[] are distinct
if (arr[l] == x) l--;
// Compare elements on left and right of
// crossover point to find the k closest
// elements
while (l >= 0 && r < n && count < k)
{
if (x - arr[l] < arr[r] - x)
Console.Write(arr[l--]+" ");
else
Console.Write(arr[r++]+" ");
count++;
}
// If there are no more elements on right
// side, then print left elements
while (count < k && l >= 0)
{
Console.Write(arr[l--]+" ");
count++;
}
// If there are no more elements on left
// side, then print right elements
while (count < k && r < n)
{
Console.Write(arr[r++] + " ");
count++;
}
}
/* Driver program to check above functions */
public static void Main()
{
int []arr = {12, 16, 22, 30, 35, 39, 42,
45, 48, 50, 53, 55, 56};
int n = arr.Length;
int x = 35;
printKclosest(arr, x, 4, n);
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP Program to Find k closest
// elements to a given value
/* Function to find the cross
over point (the point before
which elements are smaller
than or equal to x and after
which greater than x) */
function findCrossOver($arr, $low,
$high, $x)
{
// Base cases
// x is greater than all
if ($arr[$high] <= $x)
return $high;
// x is smaller than all
if ($arr[$low] > $x)
return $low;
// Find the middle point
/* low + (high - low)/2 */
$mid = ($low + $high)/2;
/* If x is same as middle
element, then return mid */
if ($arr[$mid] <= $x and
$arr[$mid + 1] > $x)
return $mid;
/* If x is greater than arr[mid],
then either arr[mid + 1] is
ceiling of x or ceiling lies
in arr[mid+1...high] */
if($arr[$mid] < $x)
return findCrossOver($arr, $mid + 1,
$high, $x);
return findCrossOver($arr, $low,
$mid - 1, $x);
}
// This function prints k
// closest elements to x in arr[].
// n is the number of elements
// in arr[]
function printKclosest($arr, $x, $k, $n)
{
// Find the crossover point
$l = findCrossOver($arr, 0, $n - 1, $x);
// Right index to search
$r = $l + 1;
// To keep track of count of
// elements already printed
$count = 0;
// If x is present in arr[],
// then reduce left index
// Assumption: all elements
// in arr[] are distinct
if ($arr[$l] == $x) $l--;
// Compare elements on left
// and right of crossover
// point to find the k
// closest elements
while ($l >= 0 and $r < $n
and $count < $k)
{
if ($x - $arr[$l] < $arr[$r] - $x)
echo $arr[$l--]," ";
else
echo $arr[$r++]," ";
$count++;
}
// If there are no more
// elements on right side,
// then print left elements
while ($count < $k and $l >= 0)
echo $arr[$l--]," "; $count++;
// If there are no more
// elements on left side,
// then print right elements
while ($count < $k and $r < $n)
echo $arr[$r++]; $count++;
}
// Driver Code
$arr =array(12, 16, 22, 30, 35, 39, 42,
45, 48, 50, 53, 55, 56);
$n = count($arr);
$x = 35; $k = 4;
printKclosest($arr, $x, 4, $n);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// JavaScript program to find k
// closest elements to a given value
// Function to find the cross over point
// (the point before which elements are
// smaller than or equal to x and after
// which greater than x)
function findCrossOver(arr, low, high, x)
{
// Base cases
if (arr[high] <= x) // x is greater than all
return high
if (arr[low] > x) // x is smaller than all
return low
// Find the middle point
var mid = (low + high) // 2 // low + (high - low)// 2
// If x is same as middle element,
// then return mid
if (arr[mid] <= x && arr[mid + 1] > x)
return mid
// If x is greater than arr[mid], then
// either arr[mid + 1] is ceiling of x
// or ceiling lies in arr[mid+1...high]
if (arr[mid] < x)
return findCrossOver(arr, mid + 1, high, x)
return findCrossOver(arr, low, mid - 1, x)
}
// This function prints k closest elements to x
// in arr[]. n is the number of elements in arr[]
function printKclosest(arr, x, k, n)
{
// Find the crossover point
var l = findCrossOver(arr, 0, n - 1, x)
var r = l + 1 // Right index to search
var count = 0 // To keep track of count of
// elements already printed
// If x is present in arr[], then reduce
// left index. Assumption: all elements
// in arr[] are distinct
if (arr[l] == x)
l -= 1
// Compare elements on left and right of crossover
// point to find the k closest elements
while (l >= 0 && r < n && count < k)
{
if (x - arr[l] < arr[r] - x)
{
document.write(arr[l] + " ")
l -= 1
}
else
{
document.write(arr[r] + " ")
r += 1
}
count += 1
}
// If there are no more elements on right
// side, then print left elements
while (count < k && l >= 0)
{
print(arr[l])
l -= 1
count += 1
}
// If there are no more elements on left
// side, then print right elements
while (count < k && r < n)
{
print(arr[r])
r += 1
count += 1
}
}
// Driver Code
var arr = [ 12, 16, 22, 30, 35, 39, 42,
45, 48, 50, 53, 55, 56 ]
var n = arr.length
var x = 35
var k = 4
printKclosest(arr, x, 4, n)
// This code is contributed by AnkThon
</script>
Producción
39 30 42 45
La complejidad temporal de este método es O(Logn + k).
Ejercicio: Amplíe la solución optimizada para trabajar también con duplicados, es decir, para trabajar con arreglos donde los elementos no tienen que ser distintos.
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