leetcode

commit 3ba74068c5d5089d6fe5b0e19a650fdfa09c74da
parent e48442b51718815055f3dce312c7b093b82b0c7e
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Thu, 21 Nov 2024 19:52:14 +0100

1 Random Problem

Diffstat:
A
Problems/0658.cpp
 | 
25
+++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 26 insertions(+), 0 deletions(-)
diff --git a/Problems/0658.cpp b/Problems/0658.cpp
@@ -0,0 +1,25 @@
+class Solution {
+  public:
+    vector<int> findClosestElements(const vector<int> &arr, int k, int x) const {
+        const int n = size(arr);
+
+        const auto mid = upper_bound(begin(arr), end(arr), x);
+        if (mid == end(arr)) return vector(begin(arr) + n - k, end(arr));
+
+        int j = distance(begin(arr), mid), i = j - 1;
+        int a = 0, b = k - 1;
+        vector<int> res(k);
+
+        while (a <= b) {
+            if (j < n && (i < 0 || x - arr[i] > arr[j] - x))
+                res[b--] = arr[j++];
+            else
+                res[a++] = arr[i--];
+        }
+
+        reverse(begin(res), begin(res) + a);
+        reverse(begin(res) + b + 1, end(res));
+
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -514,6 +514,7 @@ reference and a base for solving problems.
 |  0653  |    Easy    | [Two Sum IV - Input is a BST](Problems/0653.cpp)                                                   |
 |  0654  |   Medium   | [Maximum Binary Tree](Problems/0654.cpp)                                                           |
 |  0655  |   Medium   | [Print Binary Tree](Problems/0655.cpp)                                                             |
+|  0658  |   Medium   | [Find K Closest Elements](Problems/0658.cpp)                                                       |
 |  0659  |   Medium   | [Split Array into Consecutive Subsequences](Problems/0659.cpp)                                     |
 |  0661  |    Easy    | [Image Smoother](Problems/0661.cpp)                                                                |
 |  0662  |   Medium   | [Maximum Width of Binary Tree](Problems/0662.cpp)                                                  |