Find k closest numbers in an unsorted array
Here given code implementation process.
//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
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