Find k closest numbers in an unsorted array
In various applications, it's often necessary to find the K closest numbers to a given value X in an unsorted array. This problem requires sorting the array and then selecting the K closest elements to the target value. In this article, we'll explore a C program that solves this problem efficiently using a heap-based approach.
Problem Statement and Description
Given an unsorted array and two integers, X and K, the task is to find and display the K closest elements to the
value X in the array. The array is unsorted, so we need to first sort it before identifying the K closest
elements. For example, consider the array arr = {4, 2, 1, 10, 15, 17, 20, 14, 5}
, X = 9, and K = 4.
We want to find the 4 closest elements to 9 in the given array.
Idea to Solve the Problem
To solve this problem, we'll use a heap-based approach. We'll implement a min-heap that allows us to efficiently retrieve the K smallest (closest) elements from the array after sorting it. The steps include:
- Sort the array using a heap sort.
- Find the location of the first element in the array that is less than or equal to X.
- Initialize two pointers, one pointing to the found location and another to the element just before it.
- Compare the absolute differences of the current two pointers' elements with X. Select the element with the smaller difference and move the respective pointer accordingly.
- Repeat this process K times to find the K closest elements.
Pseudocode
function swap(arr, first, second)
// Swaps two elements in the array
function compare(arr, left, right, root, size)
// Compares elements and returns the index of the smaller element
function heap(arr, size, root)
// Creates a min-heap
function sort_element(arr, size)
// Sorts the array using heap sort
function difference(arr, i, j, x)
// Compares the absolute differences between arr[i] and arr[j] with x
function closest_k(arr, size, x, k)
sort_element(arr, size)
location = find_location(arr, size, x)
back = location - 1
i = 0
while i < k
temp = difference(arr, back, location, x)
print arr[temp]
if temp == location
location++
else
back--
i++
function main()
arr = {4, 2, 1, 10, 15, 17, 20, 14, 5}
size = sizeof(arr) / sizeof(arr[0])
x = 9, k = 4
closest_k(arr, size, x, k)
Algorithm Explanation
- The
swap
function swaps two elements in the array. - The
compare
function compares the elements at indicesleft
andright
with the element at indexroot
and returns the index of the smaller element. - The
heap
function creates a min-heap by comparing elements and swapping them if needed. - The
sort_element
function sorts the array using heap sort by repeatedly calling theheap
function. - The
difference
function calculates the absolute differences between two elements and the valuex
, then returns the index of the element with the smaller difference. - The
closest_k
function sorts the array, finds the initial location, and iterates to find the K closest elements. It prints each element found. - In the
main
function, the given array is initialized, and theclosest_k
function is called to find and display the K closest elements to the given value X.
Code Solution
//C Program
//Find k closest numbers in an unsorted array
#include <stdio.h>
//Swap two element in array
void swap(int arr[],int first,int second)
{
int auxiliary=arr[first];
arr[first]=arr[second];
arr[second]=auxiliary;
}
int compare(int arr[],int left,int right,int root,int size)
{
int location = -1;
if(left < size && arr[left] > arr[root] )
{
if(right < size && arr[right] > arr[left])
{
swap(arr,right,root);
location = right;
}
else
{
swap(arr,left,root);
location = left;
}
}
else if(right < size && arr[right] > arr[root])
{
swap(arr,right,root);
location = right;
}
return location;
}
void heap(int arr[],int size,int root)
{
int left = 2*root+1;
int right = 2*root+2;
int next_in = compare(arr, left, right, root, size);
if(next_in != -1)
{
heap(arr,size,next_in);
}
}
void print_array(int arr[],int size)
{
printf("\n");
for(int i = 0; i < size; i++)
{
printf("%3d",arr[i] );
}
}
void sort_element(int arr[],int size)
{
for (int i = (size/2)-1; i >= 0; i--)
{
heap(arr,size,i);
}
for (int i = size-1; i >= 0; i--)
{
swap(arr, 0, i);
heap(arr, i, 0);
}
}
//Compare the value of i and j to value x and return smallest difference location
int difference(int arr[],int i,int j,int x)
{
int first = arr[i]-x;
int second = arr[j]-x;
if(first<0)
{
first=-first;
}
if(second<0)
{
second=-second;
}
if(first > second)
{
return j;
}
else
{
return i;
}
}
//Display k closest elements of value x in given array
void closest_k(int arr[],int size,int x,int k)
{
if(k > size)
{
//invalid possibility
return;
}
//first sort array element
sort_element(arr,size);
int location=-1,back=0,i=0,temp=0;
//Find First element which is less than or equal to given value x
for (i = 0; i < size; ++i)
{
if(x <= arr[i])
{
location = i;
break;
}
}
if(location==-1)
{
if(x > arr[size-1])
{
//point to last element
location = size-1;
}
else
{
//point to first element
location = 0;
}
}
back=location-1;
printf(" Nearest %d elements of value %d is :\n",k,x );
i = 0;
while(i < k)
{
if(location <size && back>-1)
{
temp = difference(arr,back,location,x);
printf(" %d ",arr[temp] );
if(temp == location)
{
location++;
}
else
{
back--;
}
}
else if(location < size)
{
printf(" %d ",arr[location] );
location++;
}
else if(back>0)
{
printf(" %d",arr[back] );
back--;
}
i++;
}
printf("\n");
}
int main()
{
//Define Collection of array elements
int arr[] = {4, 2, 1, 10, 15, 17, 20 , 14, 5};
//Get the size of array
int size = sizeof(arr)/sizeof(arr[0]);
// x is value
// k is size of closest element
int x = 9, k = 4;
closest_k(arr,size,x,k);
return 0;
}
Output
Nearest 4 elements of value 9 is :
10 5 4 14
#include<iostream>
using namespace std;
/*
C++ Program
Find k closest numbers in an unsorted array
*/
class MyHeap {
public:
//Swap two element in array
void swap(int arr[], int first, int second) {
int auxiliary = arr[first];
arr[first] = arr[second];
arr[second] = auxiliary;
}
int compare(int arr[], int left, int right, int root, int size) {
int location = -1;
if (left < size && arr[left] > arr[root]) {
if (right < size && arr[right] > arr[left]) {
this->swap(arr, right, root);
location = right;
} else {
this->swap(arr, left, root);
location = left;
}
} else
if (right < size && arr[right] > arr[root]) {
this->swap(arr, right, root);
location = right;
}
return location;
}
void heap(int arr[], int size, int root) {
int left = 2 *root + 1;
int right = 2 *root + 2;
int next_in = this->compare(arr, left, right, root, size);
if (next_in != -1) {
this->heap(arr, size, next_in);
}
}
void print_array(int arr[], int size) {
cout << "\n";
for (int i = 0; i < size; i++) {
cout << " " << arr[i];
}
}
void sort_element(int arr[], int size) {
for (int i = (size / 2) - 1; i >= 0; i--) {
this->heap(arr, size, i);
}
for (int i = size - 1; i >= 0; i--) {
this->swap(arr, 0, i);
this->heap(arr, i, 0);
}
}
//Compare the value of i and j to value x and return smallest difference location
int difference(int arr[], int i, int j, int x) {
int first = arr[i] - x;
int second = arr[j] - x;
if (first < 0) {
first = -first;
}
if (second < 0) {
second = -second;
}
if (first > second) {
return j;
} else {
return i;
}
}
//Display k closest elements of value x in given array
void closest_k(int arr[], int size, int x, int k) {
if (k > size) {
//invalid possibility
return;
}
//first sort array element
this->sort_element(arr, size);
int location = -1, back = 0, i = 0, temp = 0;
//Find First element which is less than or equal to given value x
for (i = 0; i < size; ++i) {
if (x <= arr[i]) {
location = i;
break;
}
}
if (location == -1) {
if (x > arr[size - 1]) {
//point to last element
location = size - 1;
} else {
//point to first element
location = 0;
}
}
back = location - 1;
i = 0;
cout << " Nearest " << k << " elements of value " << x << " is :\n";
while (i < k) {
if (location < size && back > -1) {
temp = this->difference(arr, back, location, x);
cout << " " << arr[temp];
if (temp == location) {
location++;
} else {
back--;
}
i++;
} else
if (location < size) {
cout << " " << arr[location];
location++;
i++;
} else
if (back > 0) {
cout << " " << arr[location];
back--;
i++;
}
}
cout << "\n";
}
};
int main() {
MyHeap obj = MyHeap();
int arr[] = {
4,
2,
1,
10,
15,
17,
20,
14,
5
};
//Get the size of array
int size = sizeof(arr) / sizeof(arr[0]);
// x is value
// k is size of closest element
int x = 9, k = 4;
obj.closest_k(arr, size, x, k);
return 0;
}
Output
Nearest 4 elements of value 9 is :
10 5 4 14
/*
Java Program
Find k closest numbers in an unsorted array
*/
public class MyHeap {
//Swap two element in array
public void swap(int []arr,int first,int second)
{
int auxiliary=arr[first];
arr[first]=arr[second];
arr[second]=auxiliary;
}
public int compare(int []arr,int left,int right,int root,int size)
{
int location = -1;
if(left < size && arr[left] > arr[root] )
{
if(right < size && arr[right] > arr[left])
{
swap(arr,right,root);
location = right;
}
else
{
swap(arr,left,root);
location = left;
}
}
else if(right < size && arr[right] > arr[root])
{
swap(arr,right,root);
location = right;
}
return location;
}
public void heap(int []arr,int size,int root)
{
int left = 2*root+1;
int right = 2*root+2;
int next_in = compare(arr, left, right, root, size);
if(next_in != -1)
{
heap(arr,size,next_in);
}
}
public void print_array(int []arr,int size)
{
System.out.print("\n");
for(int i = 0; i < size; i++)
{
System.out.print(" "+arr[i] );
}
}
public void sort_element(int []arr,int size)
{
for (int i = (size/2)-1; i >= 0; i--)
{
heap(arr,size,i);
}
for (int i = size-1; i >= 0; i--)
{
swap(arr, 0, i);
heap(arr, i, 0);
}
}
//Compare the value of i and j to value x and return smallest difference location
public int difference(int []arr,int i,int j,int x)
{
int first = arr[i]-x;
int second = arr[j]-x;
if(first<0)
{
first=-first;
}
if(second<0)
{
second=-second;
}
if(first > second)
{
return j;
}
else
{
return i;
}
}
//Display k closest elements of value x in given array
public void closest_k(int []arr,int size,int x,int k)
{
if(k > size)
{
//invalid possibility
return;
}
//first sort array element
sort_element(arr,size);
int location=-1,back=0,i=0,temp=0;
//Find First element which is less than or equal to given value x
for (i = 0; i < size; ++i)
{
if(x <= arr[i])
{
location = i;
break;
}
}
if(location==-1)
{
if(x > arr[size-1])
{
//point to last element
location = size-1;
}
else
{
//point to first element
location = 0;
}
}
back=location-1;
i = 0;
System.out.print(" Nearest "+k+" elements of value "+x+" is :\n");
while(i < k)
{
if(location <size && back>-1)
{
temp = difference(arr,back,location,x);
System.out.print(" "+arr[temp] );
if(temp == location)
{
location++;
}
else
{
back--;
}
i++;
}
else if(location < size)
{
System.out.print(" "+arr[location] );
location++;
i++;
}
else if(back>0)
{
System.out.print(" "+arr[location] );
back--;
i++;
}
}
System.out.print("\n");
}
public static void main(String[] args) {
MyHeap obj = new MyHeap();
//Define Collection of array elements
int []arr = {4, 2, 1, 10, 15, 17, 20 , 14, 5};
//Get the size of array
int size = arr.length;
// x is value
// k is size of closest element
int x = 9, k = 4;
obj.closest_k(arr,size,x,k);
}
}
Output
Nearest 4 elements of value 9 is :
10 5 4 14
/*
C# Program
Find k closest numbers in an unsorted array
*/
using System;
public class MyHeap {
//Swap two element in array
public void swap(int[] arr, int first, int second) {
int auxiliary = arr[first];
arr[first] = arr[second];
arr[second] = auxiliary;
}
public int compare(int[] arr, int left, int right, int root, int size) {
int location = -1;
if (left < size && arr[left] > arr[root]) {
if (right < size && arr[right] > arr[left]) {
swap(arr, right, root);
location = right;
} else {
swap(arr, left, root);
location = left;
}
} else
if (right < size && arr[right] > arr[root]) {
swap(arr, right, root);
location = right;
}
return location;
}
public void heap(int[] arr, int size, int root) {
int left = 2 * root + 1;
int right = 2 * root + 2;
int next_in = compare(arr, left, right, root, size);
if (next_in != -1) {
heap(arr, size, next_in);
}
}
public void print_array(int[] arr, int size) {
Console.Write("\n");
for (int i = 0; i < size; i++) {
Console.Write(" " + arr[i]);
}
}
public void sort_element(int[] arr, int size) {
for (int i = (size / 2) - 1; i >= 0; i--) {
heap(arr, size, i);
}
for (int i = size - 1; i >= 0; i--) {
swap(arr, 0, i);
heap(arr, i, 0);
}
}
//Compare the value of i and j to value x and return smallest difference location
public int difference(int[] arr, int i, int j, int x) {
int first = arr[i] - x;
int second = arr[j] - x;
if (first < 0) {
first = -first;
}
if (second < 0) {
second = -second;
}
if (first > second) {
return j;
} else {
return i;
}
}
//Display k closest elements of value x in given array
public void closest_k(int[] arr, int size, int x, int k) {
if (k > size) {
return;
}
sort_element(arr, size);
int location = -1, back = 0, i = 0, temp = 0;
//Find First element which is less than or equal to given value x
for (i = 0; i < size; ++i) {
if (x <= arr[i]) {
location = i;
break;;
}
}
if (location == -1) {
if (x > arr[size - 1]) {
//point to last element
location = size - 1;
} else {
//point to first element
location = 0;
}
}
back = location - 1;
i = 0;
Console.Write(" Nearest " + k + " elements of value " + x + " is :\n");
while (i < k) {
if (location < size && back > -1) {
temp = difference(arr, back, location, x);
Console.Write(" " + arr[temp]);
if (temp == location) {
location++;
} else {
back--;
}
i++;
} else
if (location < size) {
Console.Write(" " + arr[location]);
location++;
i++;
} else
if (back > 0) {
Console.Write(" " + arr[location]);
back--;
i++;
}
}
Console.Write("\n");
}
public static void Main(String[] args) {
MyHeap obj = new MyHeap();
int[]
//Define Collection of array elements
arr = {
4,
2,
1,
10,
15,
17,
20,
14,
5
};
//Get the size of array
int size = arr.Length;
// x is value
// k is size of closest element
int x = 9, k = 4;
obj.closest_k(arr, size, x, k);
}
}
Output
Nearest 4 elements of value 9 is :
10 5 4 14
<?php
/*
Php Program
Find k closest numbers in an unsorted array
*/
class MyHeap {
//Swap two element in array
public function swap(&$arr, $first, $second) {
$auxiliary = $arr[$first];
$arr[$first] = $arr[$second];
$arr[$second] = $auxiliary;
}
public function compare(&$arr, $left, $right, $root, $size) {
$location = -1;
if ($left < $size && $arr[$left] > $arr[$root]) {
if ($right < $size && $arr[$right] > $arr[$left]) {
$this->swap($arr, $right, $root);
$location = $right;
} else {
$this->swap($arr, $left, $root);
$location = $left;
}
} else
if ($right < $size && $arr[$right] > $arr[$root]) {
$this->swap($arr, $right, $root);
$location = $right;
}
return $location;
}
public function heap(&$arr, $size, $root) {
$left = 2 *$root + 1;
$right = 2 *$root + 2;
$next_in = $this->compare($arr, $left, $right, $root, $size);
if ($next_in != -1) {
$this->heap($arr, $size, $next_in);
}
}
public function print_array($arr, $size) {
echo("\n");
for ($i = 0; $i < $size; $i++) {
echo(" ". $arr[$i]);
}
}
public function sort_element(&$arr, $size) {
for ($i = (intval($size / 2)) - 1; $i >= 0; $i--) {
$this->heap($arr, $size, $i);
}
for ($i = $size - 1; $i >= 0; $i--) {
$this->swap($arr, 0, $i);
$this->heap($arr, $i, 0);
}
}
//Compare the value of i and j to value x and return smallest difference location
public function difference($arr, $i, $j, $x) {
$first = $arr[$i] - $x;
$second = $arr[$j] - $x;
if ($first < 0) {
$first = -$first;
}
if ($second < 0) {
$second = -$second;
}
if ($first > $second) {
return $j;
} else {
return $i;
}
}
//Display k closest elements of value x in given array
public function closest_k(&$arr, $size, $x, $k) {
if ($k > $size) {
return;
}
//first sort array element
$this->sort_element($arr, $size);
$location = -1;
$back = 0;
$i = 0;
$temp = 0;
//Find First element which is less than or equal to given value x
for ($i = 0; $i < $size; ++$i) {
if ($x <= $arr[$i]) {
$location = $i;
break;
}
}
if ($location == -1) {
if ($x > $arr[$size - 1]) {
//point to last element
$location = $size - 1;
} else {
//point to first element
$location = 0;
}
}
$back = $location - 1;
$i = 0;
echo(" Nearest ". $k ." elements of value ". $x ." is :\n");
while ($i < $k) {
if ($location < $size && $back > -1) {
$temp = $this->difference($arr, $back, $location, $x);
echo(" ". $arr[$temp]);
if ($temp == $location) {
$location++;
} else {
$back--;
}
$i++;
} else
if ($location < $size) {
echo(" ". $arr[$location]);
$location++;
$i++;
} else
if ($back > 0) {
echo(" ". $arr[$location]);
$back--;
$i++;
}
}
echo("\n");
}
}
function main() {
$obj = new MyHeap();
//Define Collection of array elements
$arr = array(4, 2, 1, 10, 15, 17, 20, 14, 5);
//Get the size of array
$size = count($arr);
// x is value
// k is size of closest element
$x = 9;
$k = 4;
$obj->closest_k($arr, $size, $x, $k);
}
main();
Output
Nearest 4 elements of value 9 is :
10 5 4 14
/*
Node Js Program
Find k closest numbers in an unsorted array
*/
class MyHeap {
//Swap two element in array
swap(arr, first, second) {
var auxiliary = arr[first];
arr[first] = arr[second];
arr[second] = auxiliary;
}
compare(arr, left, right, root, size) {
var location = -1;
if (left < size && arr[left] > arr[root]) {
if (right < size && arr[right] > arr[left]) {
this.swap(arr, right, root);
location = right;
} else {
this.swap(arr, left, root);
location = left;
}
} else
if (right < size && arr[right] > arr[root]) {
this.swap(arr, right, root);
location = right;
}
return location;
}
heap(arr, size, root) {
var left = 2 *root + 1;
var right = 2 *root + 2;
var next_in = this.compare(arr, left, right, root, size);
if (next_in != -1) {
this.heap(arr, size, next_in);
}
}
print_array(arr, size) {
process.stdout.write("\n");
for (var i = 0; i < size; i++) {
process.stdout.write(" " + arr[i]);
}
}
sort_element(arr, size) {
for (var i = (parseInt(size / 2)) - 1; i >= 0; i--) {
this.heap(arr, size, i);
}
for (var i = size - 1; i >= 0; i--) {
this.swap(arr, 0, i);
this.heap(arr, i, 0);
}
}
//Compare the value of i and j to value x and return smallest difference location
difference(arr, i, j, x) {
var first = arr[i] - x;
var second = arr[j] - x;
if (first < 0) {
first = -first;
}
if (second < 0) {
second = -second;
}
if (first > second) {
return j;
} else {
return i;
}
}
//Display k closest elements of value x in given array
closest_k(arr, size, x, k) {
if (k > size) {
return;
}
//first sort array element
this.sort_element(arr, size);
var location = -1;
var back = 0;
var i = 0;
var temp = 0;
//Find First element which is less than or equal to given value x
for (i = 0; i < size; ++i) {
if (x <= arr[i]) {
location = i;
break;
}
}
if (location == -1) {
if (x > arr[size - 1]) {
//point to last element
location = size - 1;
} else {
//point to first element
location = 0;
}
}
back = location - 1;
i = 0;
process.stdout.write(" Nearest " + k + " elements of value " + x + " is :\n");
while (i < k) {
if (location < size && back > -1) {
temp = this.difference(arr, back, location, x);
process.stdout.write(" " + arr[temp]);
if (temp == location) {
location++;
} else {
back--;
}
i++;
} else
if (location < size) {
process.stdout.write(" " + arr[location]);
location++;
i++;
} else
if (back > 0) {
process.stdout.write(" " + arr[location]);
back--;
i++;
}
}
process.stdout.write("\n");
}
}
function main(args) {
var obj = new MyHeap();
//Define Collection of array elements
var arr = [4, 2, 1, 10, 15, 17, 20, 14, 5];
//Get the size of array
var size = arr.length;
// x is value
// k is size of closest element
var x = 9;
var k = 4;
obj.closest_k(arr, size, x, k);
}
main();
Output
Nearest 4 elements of value 9 is :
10 5 4 14
# Python 3 Program
# Find k closest numbers in an unsorted array
class MyHeap :
# Swap two element in array
def swap(self, arr, first, second) :
auxiliary = arr[first]
arr[first] = arr[second]
arr[second] = auxiliary
def compare(self, arr, left, right, root, size) :
location = -1
if (left < size and arr[left] > arr[root]) :
if (right < size and arr[right] > arr[left]) :
self.swap(arr, right, root)
location = right
else :
self.swap(arr, left, root)
location = left
elif (right < size and arr[right] > arr[root]) :
self.swap(arr, right, root)
location = right
return location
def heap(self, arr, size, root) :
left = 2 * root + 1
right = 2 * root + 2
next_in = self.compare(arr, left, right, root, size)
if (next_in != -1) :
self.heap(arr, size, next_in)
def print_array(self, arr, size) :
print("\n", end = "")
i = 0
while (i < size) :
print(" ", arr[i], end = "")
i += 1
def sort_element(self, arr, size) :
i = (int(size / 2)) - 1
while (i >= 0) :
self.heap(arr, size, i)
i -= 1
i = size - 1
while (i >= 0) :
self.swap(arr, 0, i)
self.heap(arr, i, 0)
i -= 1
# Compare the value of i and j to value x and return smallest difference location
def difference(self, arr, i, j, x) :
first = arr[i] - x
second = arr[j] - x
if (first < 0) :
first = -first
if (second < 0) :
second = -second
if (first > second) :
return j
else :
return i
# Display k closest elements of value x in given array
def closest_k(self, arr, size, x, k) :
if (k > size) :
return
self.sort_element(arr, size)
location = -1
back = 0
i = 0
temp = 0
# Find First element which is less than or equal to given value x
i = 0
while (i < size) :
if (x <= arr[i]) :
location = i
break
i += 1
if (location == -1) :
if (x > arr[size - 1]) :
# point to last element
location = size - 1
else :
# point to first element
location = 0
back = location - 1
i = 0
print(" Nearest ", k ," elements of value ", x ," is :\n", end = "")
while (i < k) :
if (location < size and back > -1) :
temp = self.difference(arr, back, location, x)
print(" ", arr[temp], end = "")
if (temp == location) :
location += 1
else :
back -= 1
i += 1
elif (location < size) :
print(" ", arr[location], end = "")
location += 1
i += 1
elif (back > 0) :
print(" ", arr[location], end = "")
back -= 1
i += 1
print("\n", end = "")
def main() :
obj = MyHeap()
# Define Collection of array elements
arr = [4, 2, 1, 10, 15, 17, 20, 14, 5]
# Get the size of array
size = len(arr)
# k is size of closest element
# x is value
# k is size of closest element
x = 9
k = 4
obj.closest_k(arr, size, x, k)
if __name__ == "__main__":
main()
Output
Nearest 4 elements of value 9 is :
10 5 4 14
# Ruby Program
# Find k closest numbers in an unsorted array
class MyHeap
# Swap two element in array
def swap(arr, first, second)
auxiliary = arr[first]
arr[first] = arr[second]
arr[second] = auxiliary
end
def compare(arr, left, right, root, size)
location = -1
if (left < size && arr[left] > arr[root])
if (right < size && arr[right] > arr[left])
self.swap(arr, right, root)
location = right
else
self.swap(arr, left, root)
location = left
end
elsif (right < size && arr[right] > arr[root])
self.swap(arr, right, root)
location = right
end
return location
end
def heap(arr, size, root)
left = 2 * root + 1
right = 2 * root + 2
next_in = self.compare(arr, left, right, root, size)
if (next_in != -1)
self.heap(arr, size, next_in)
end
end
def print_array(arr, size)
print("\n")
i = 0
while (i < size)
print(" ", arr[i])
i += 1
end
end
def sort_element(arr, size)
i = (size / 2) - 1
while (i >= 0)
self.heap(arr, size, i)
i -= 1
end
i = size - 1
while (i >= 0)
self.swap(arr, 0, i)
self.heap(arr, i, 0)
i -= 1
end
end
# Compare the value of i and j to value x and return smallest difference location
def difference(arr, i, j, x)
first = arr[i] - x
second = arr[j] - x
if (first < 0)
first = -first
end
if (second < 0)
second = -second
end
if (first > second)
return j
else
return i
end
end
# Display k closest elements of value x in given array
def closest_k(arr, size, x, k)
if (k > size)
return
end
self.sort_element(arr, size)
location = -1
back = 0
i = 0
temp = 0
# Find First element which is less than or equal to given value x
i = 0
while (i < size)
if (x <= arr[i])
location = i
break
end
i += 1
end
if (location == -1)
if (x > arr[size - 1])
# point to last element
location = size - 1
else
# point to first element
location = 0
end
end
back = location - 1
i = 0
print(" Nearest ", k ," elements of value ", x ," is :\n")
while (i < k)
if (location < size && back > -1)
temp = self.difference(arr, back, location, x)
print(" ", arr[temp])
if (temp == location)
location += 1
else
back -= 1
end
i += 1
elsif (location < size)
print(" ", arr[location])
location += 1
i += 1
elsif (back > 0)
print(" ", arr[location])
back -= 1
i += 1
end
end
print("\n")
end
end
def main()
obj = MyHeap.new()
# Define Collection of array elements
arr = [4, 2, 1, 10, 15, 17, 20, 14, 5]
# Get the size of array
size = arr.length
# k is size of closest element
# x is value
# k is size of closest element
x = 9
k = 4
obj.closest_k(arr, size, x, k)
end
main()
Output
Nearest 4 elements of value 9 is :
10 5 4 14
/*
Scala Program
Find k closest numbers in an unsorted array
*/
class MyHeap {
//Swap two element in array
def swap(arr: Array[Int], first: Int, second: Int): Unit = {
val auxiliary: Int = arr(first);
arr(first) = arr(second);
arr(second) = auxiliary;
}
def compare(arr: Array[Int], left: Int, right: Int, root: Int, size: Int): Int = {
var location: Int = -1;
if (left < size && arr(left) > arr(root)) {
if (right < size && arr(right) > arr(left)) {
this.swap(arr, right, root);
location = right;
} else {
this.swap(arr, left, root);
location = left;
}
} else
if (right < size && arr(right) > arr(root)) {
this.swap(arr, right, root);
location = right;
}
return location;
}
def heap(arr: Array[Int], size: Int, root: Int): Unit = {
val left: Int = 2 * root + 1;
val right: Int = 2 * root + 2;
val next_in: Int = this.compare(arr, left, right, root, size);
if (next_in != -1) {
this.heap(arr, size, next_in);
}
}
def print_array(arr: Array[Int], size: Int): Unit = {
print("\n");
var i: Int = 0;
while (i < size) {
print(" " + arr(i));
i += 1;
}
}
def sort_element(arr: Array[Int], size: Int): Unit = {
var i: Int = ((size / 2).toInt) - 1;
while (i >= 0) {
this.heap(arr, size, i);
i -= 1;
}
i = size - 1;
while (i >= 0) {
this.swap(arr, 0, i);
this.heap(arr, i, 0);
i -= 1;
}
}
//Compare the value of i and j to value x and return smallest difference location
def difference(arr: Array[Int], i: Int, j: Int, x: Int): Int = {
var first: Int = arr(i) - x;
var second: Int = arr(j) - x;
if (first < 0) {
first = -first;
}
if (second < 0) {
second = -second;
}
if (first > second) {
return j;
} else {
return i;
}
}
//Display k closest elements of value x in given array
def closest_k(arr: Array[Int], size: Int, x: Int, k: Int): Unit = {
if (k > size) {
return;
}
this.sort_element(arr, size);
var location: Int = -1;
var back: Int = 0;
var i: Int = 0;
var temp: Int = 0;
//Find First element which is less than or equal to given value x
i = 0;
while (i < size && location == -1) {
if (x <= arr(i)) {
location = i;
}
i += 1;
}
if (location == -1) {
if (x > arr(size - 1)) {
//point to last element
location = size - 1;
} else {
//point to first element
location = 0;
}
}
back = location - 1;
i = 0;
print(" Nearest " + k + " elements of value " + x + " is :\n");
while (i < k) {
if (location < size && back > -1) {
temp = this.difference(arr, back, location, x);
print(" " + arr(temp));
if (temp == location) {
location += 1;
} else {
back -= 1;
}
i += 1;
} else
if (location < size) {
print(" " + arr(location));
location += 1;
i += 1;
} else
if (back > 0) {
print(" " + arr(location));
back -= 1;
i += 1;
}
}
print("\n");
}
}
object Main {
def main(args: Array[String]): Unit = {
val obj: MyHeap = new MyHeap();
//Define Collection of array elements
var arr: Array[Int] = Array(4, 2, 1, 10, 15, 17, 20, 14, 5);
//Get the size of array
val size: Int = arr.length;
// x is value
// k is size of closest element
val x: Int = 9;
val k: Int = 4;
obj.closest_k(arr, size, x, k);
}
}
Output
Nearest 4 elements of value 9 is :
10 5 4 14
/*
Swift Program
Find k closest numbers in an unsorted array
*/
class MyHeap {
//Swap two element in array
func swap(_ arr: inout [Int], _ first: Int, _ second: Int) {
let auxiliary: Int = arr[first];
arr[first] = arr[second];
arr[second] = auxiliary;
}
func compare(_ arr: inout [Int], _ left: Int, _ right: Int, _ root: Int, _ size: Int) -> Int {
var location: Int = -1;
if (left < size && arr[left] > arr[root]) {
if (right < size && arr[right] > arr[left]) {
self.swap(&arr, right, root);
location = right;
} else {
self.swap(&arr, left, root);
location = left;
}
} else
if (right < size && arr[right] > arr[root]) {
self.swap(&arr, right, root);
location = right;
}
return location;
}
func heap(_ arr: inout [Int], _ size: Int, _ root: Int) {
let left: Int = 2 * root + 1;
let right: Int = 2 * root + 2;
let next_in: Int = self.compare(&arr, left, right, root, size);
if (next_in != -1) {
self.heap(&arr, size, next_in);
}
}
func print_array(_ arr: [Int], _ size: Int) {
print("\n", terminator: "");
var i: Int = 0;
while (i < size) {
print(" ", arr[i], terminator: "");
i += 1;
}
}
func sort_element(_ arr: inout [Int], _ size: Int) {
var i: Int = (size / 2) - 1;
while (i >= 0) {
self.heap(&arr, size, i);
i -= 1;
}
i = size - 1;
while (i >= 0) {
self.swap(&arr, 0, i);
self.heap(&arr, i, 0);
i -= 1;
}
}
//Compare the value of i and j to value x and return smallest difference location
func difference(_ arr: [Int], _ i: Int, _ j: Int, _ x: Int) -> Int {
var first: Int = arr[i] - x;
var second: Int = arr[j] - x;
if (first < 0) {
first = -first;
}
if (second < 0) {
second = -second;
}
if (first > second) {
return j;
} else {
return i;
}
}
//Display k closest elements of value x in given array
func closest_k(_ arr: inout [Int], _ size: Int, _ x: Int, _ k: Int) {
if (k > size) {
return;
}
self.sort_element(&arr, size);
var location: Int = -1;
var back: Int = 0;
var i: Int = 0;
var temp: Int = 0;
//Find First element which is less than or equal to given value x
i = 0;
while (i < size) {
if (x <= arr[i]) {
location = i;
break;
}
i += 1;
}
if (location == -1) {
if (x > arr[size - 1]) {
//point to last element
location = size - 1;
} else {
//point to first element
location = 0;
}
}
back = location - 1;
i = 0;
print(" Nearest ", k ," elements of value ", x ," is :\n", terminator: "");
while (i < k) {
if (location < size && back > -1) {
temp = self.difference(arr, back, location, x);
print(" ", arr[temp], terminator: "");
if (temp == location) {
location += 1;
} else {
back -= 1;
}
i += 1;
} else
if (location < size) {
print(" ", arr[location], terminator: "");
location += 1;
i += 1;
} else
if (back > 0) {
print(" ", arr[location], terminator: "");
back -= 1;
i += 1;
}
}
print("\n", terminator: "");
}
}
func main() {
let obj: MyHeap = MyHeap();
//Define Collection of array elements
var arr: [Int] = [4, 2, 1, 10, 15, 17, 20, 14, 5];
//Get the size of array
let size: Int = arr.count;
// x is value
// k is size of closest element
let x: Int = 9;
let k: Int = 4;
obj.closest_k(&arr, size, x, k);
}
main();
Output
Nearest 4 elements of value 9 is :
10 5 4 14
Time Complexity
- The heap sort operation has an average and worst-case time complexity of O(n log n), where n is the size of the array.
- Finding the initial location takes O(n) time.
- Finding the K closest elements takes O(k log n) time.
- Overall, the time complexity is dominated by the sorting step, so the total time complexity is O(n log n).
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment