Find k closest elements to a given value
Examples:
Input: K = 4, X = 35 arr[] = {12, 16, 22, 30, 35, 39, 42, 45, 48, 50, 53, 55, 56} Output: 30 39 42 45
Note that if the element is present in array, then it should not be in output, only the other closest elements are required.
In the following solutions, it is assumed that all elements of array are distinct.
A simple solution is to do linear search for k closest elements but Binary Search would be an optimized Solution for it.
1) Start from the first element and search for the crossover point (The point before which elements are smaller than or equal to X and after which elements are greater). This step takes O(n) time.
2) Once we find the crossover point, we can compare elements on both sides of crossover point to print k closest elements. This step takes O(k) time.
The time complexity of the above solution is O(n).
An Optimized Solution is to find k elements in O(Logn + k) time. The idea is to use Binary Search to find the crossover point. Once we find index of crossover point, we can print k closest elements in O(k) time.
Sample Code Solution:
/** * @author Abhinaw.Tripathi * */ public class KClosest { public int crossOver(int arr[],int low,int high,int x) { if (arr[high] <= x) // x is greater than all return high; if (arr[low] > x) // x is smaller than all return low; int mid = (low + high)/2; if (arr[mid] <= x && arr[mid+1] > x) return mid; if(arr[mid] < x) return crossOver(arr, mid+1, high, x); return crossOver(arr, low, mid - 1, x); } public void printKclosest(int arr[], int x, int k, int n) { int l = crossOver(arr, 0, n-1, x); int r = l+1; int count = 0; if (arr[l] == x) l--;
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++; } while (count < k && l >= 0) { System.out.print(arr[l--]+" "); count++; }
while (count < k && r < n) { System.out.print(arr[r++]+" "); count++; } } 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); }
}
Output:
39 30 42 45
The time complexity of this method is O(Logn + k).