-
Notifications
You must be signed in to change notification settings - Fork 1
/
K closest elements.java
38 lines (37 loc) · 1.16 KB
/
K closest elements.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// User Template For Java
class Solution {
int[] printKClosest(int[] arr, int n, int k, int x) {
int id1 = findCrossOver(arr,0,n-1,x);
int id2 = id1+1;
if(arr[id1]==x) id1--;
int ans[] = new int[k];
for(int i=0;i<k;i++){
if(id1>=0 && id2<n){
int val1 = x-arr[id1], val2 = arr[id2]-x;
if(val1<val2){
ans[i] = arr[id1];
id1--;
}else{
ans[i] = arr[id2];
id2++; }
}else if(id1>=0){
ans[i] = arr[id1];
id1--;
}else{
ans[i] = arr[id2];
id2++; } }
return ans;
}
private int findCrossOver(int[] arr, int low, int high, int x) {
if (arr[high] <= x) {
return high; }
if (arr[low] > x) {
return low; }
int mid = (low + high) / 2;
if (arr[mid] <= x && arr[mid + 1] > x) {
return mid;
} else if (arr[mid] < x) {
return findCrossOver(arr, mid + 1, high, x);}
return findCrossOver(arr, low, mid - 1, x);
}
}