-
Notifications
You must be signed in to change notification settings - Fork 0
/
Find K Closest Elements.cpp
75 lines (61 loc) · 1.64 KB
/
Find K Closest Elements.cpp
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
class Solution {
int L, R;
int middle;
int f, l;
int q = 0;
int diff;
vector<int> res;
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
if (x < arr[0]) {
f = 0;
l = k - 1;
}
else if (x > arr[arr.size() - 1]) {
f = arr.size() - k;
l = arr.size() - 1;
}
else {
L = 0;
R = arr.size() - 1;
while(L <= R) {
middle = (L + R) >> 1;
if (arr[middle] < x)
L = middle + 1;
else
R = middle - 1;
}
if (arr[L] == x)
R = L + 1;
else {
L = abs(arr[L - 1] - x) < abs(arr[L] - x) ? L - 1 : L;
R = L + 1;
}
while(q < k) {
if (abs(arr[L] - x) <= abs(arr[R] - x)) {
f = L;
L--;
}
else {
l = R;
R++;
}
q++;
}
if (f < 0) {
diff = 0 - f;
f = 0;
l += diff;
}
else if (l > arr.size() - 1) {
diff = l - (arr.size() - 1);
f -= diff;
l = arr.size() - 1;
}
}
if (!l) l = f + k - 1;
for (int i = f; i <= l; i++)
res.push_back(arr[i]);
return res;
}
};