design and implement a (nlogn) algorithm to determine the \'K\' closest elements
ID: 3820747 • Letter: D
Question
design and implement a (nlogn) algorithm to determine the 'K' closest elements to a target value X in an array of 'n' integers. For example, consider an array A = {4, 1, 9, 7, 8, 3, 10, 2}. The three (K = 3) closest elements to integer 6 (X = 6) in this array are: {4, 7, 8}. If the target value X is in the array itself, then X is not to be considered as one of the K-Closest elements. For example, consider an array A = {4, 1, 9, 7, 8, 3, 10, 2}. The three (K = 3) closest elements to a target integer 7 (X = 7) in this array are: {4, 8, 9}. Note that {8, 9, 10} is also a valid answer in this case. As long as you print one of the valid answers, it is sufficient. In the above example (with {4, 8, 9} as the 3-closest values to '7'), the average of the 3-closest values is also 7, and the absolute difference between the target value of 7 and the average of the 3-closest values to 7 is 0. The 4-closest values to 7 are: {8, 9, 4, 10} and their average is 7.75; the absolute difference between the target value of 7 and the average of the 4-closest values to 7 is 0.75. Run simulations of your algorithm with array sizes of n = 100, 1000 and 10000. You could fill the arrays with integers randomly chosen from the range [1, ..., 500]. For each array size, vary the K values from 3 to 10. For each array size and K, conduct simulations for 50 runs (for each run, create an array for the given size and choose a random value for the target X in the range 1, ..., 500) and determine the average of the K-closest values to X as well as determine the overall average of the difference between the target X values and the average of the K-closest values to X (across the 50 simulation runs and the target X values chosen for a given array size and K). Also, determine the average execution time for each value of the array size and the different values of K.
(a) For each array size, n: plot the distribution of {K} vs. {overall average of the {difference between the target X values and the average of the K-closest values to the target X values} }
(b) For each array size, n: plot the distribution of {K} vs. average execution time. PLEASE PROVIDE CODE IN JAVA TO ENTER IN THE DIFFERENT VALUES FOR N AS ASKED IN THE QUESTION.
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);
}
} PLEASE EDIT THIS CODE SO IT CAN ANSWER THE QUESTION ASKED ABOVE
Explanation / Answer
import java.util.Arrays;
import java.util.Random;
import java.util.ArrayList;
import java.util.Collections;
// 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[]
int 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
int sum=0; //To hold the sum of k closest element
// 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){
sum+=arr[l];
System.out.print(arr[l--]+" ");
}
else
{
sum+=arr[r];
System.out.print(arr[r++]+" ");
count++;
}
}
// If there are no more elements on right side, then
// print left elements
while (count < k && l >= 0)
{
sum+=arr[l];
System.out.print(arr[l--]+" ");
count++;
}
// If there are no more elements on left side, then
// print right elements
while (count < k && r < n)
{
sum+=arr[r];
System.out.print(arr[r++]+" ");
count++;
}
//Return average of KClosest elements of an array for a given value of x
return (sum/k);
}
/* Driver program to check above functions */
public static void main(String args[])
{
KClosest ob = new KClosest();
Random rand = new Random();
int index,x,avg;
ArrayList<Integer> list = new ArrayList<Integer>();
for (int i=1; i<=500; i++) {
list.add(new Integer(i));
}
Collections.shuffle(list);
for(int n=100;n<=10000;n=n*10)
{
long startTime = System.currentTimeMillis();
//Create array of size of n
int []arr=new int[n];
//fill the array with random integers from 1 to 500
for(int i=0;i<arr.length;i++)
{
index=rand.nextInt(500);
arr[i]=list.get(index);
}
// First sort the array so that all occurrences become consecutive
Arrays.sort(arr);
//k varies from 3 to 10
for(int k=3;k<=10;k++)
{
long start = System.currentTimeMillis();
//50 runs of different values of x between 1 to 500
for(int j=1;j<=50;j++)
{
x=rand.nextInt(500) + 1;
//calling printKclosest method
avg=ob.printKclosest(arr, x, k, n);
System.out.println(" The average of "+k+" KClosest elements of an array for a given value of x="+x+" is "+avg);
int diff=java.lang.Math.abs(avg-x);
System.out.println("overall average of the difference between the target X="+x+" values and the average of the"+k+"-closest values to X is "+diff+" ");
}
long end = System.currentTimeMillis();
long total = end - start;
System.out.println(" Total Time execution for "+k+" Closest for array size "+n+" is " +total +" ms");
System.out.println(" ");
}
long endTime = System.currentTimeMillis();
long totalTime = endTime - startTime;
System.out.println(" Total Time execution for "+n+" numbers is " +totalTime +" ms");
System.out.println(" ");
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.