Skip to main content

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




Comment

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