C++ || 6 different approaches || {partial_,}sort / nth_element / binary search / two pointers / heap
Approach 1: sort, resize, sort\n\nWe could just sort all elements to find the k closests and then sort again.\n\ncpp\n    vector<int> findClosestElements(vector
### Approach 1: sort, resize, sort\n\nWe could just sort all elements to find the ```k``` closests and then sort again.\n\n```cpp\n    vector<int> findClosestElements(vector<int>& arr, int k, int x) {\n        sort(begin(arr), end(arr), [x](int a, int b) {\n            const int ad = abs(a - x);\n            const int bd = abs(b - x);\n            return ad != bd ? ad < bd : a < b;\n        });\n        arr.resize(k);\n        sort(begin(arr), end(arr));\n        return arr;\n    }\n```\n\nA variant could be to use ```stable_sort``` with that a slightly simpler sort condition could be used, because the relative order of elements is preserved. The first sort would like like this:\n\n```cpp\n        stable_sort(begin(arr), end(arr), [x](int a, int b) {\n            return abs(a - x) < abs(b - x);\n        });\n```\n\n### Approach 2: partial_sort, resize, sort\n\nThis was the first solution I wrote earlier today. Warning this solutions passes all tests, but is not entierly correct. See below.\n\n```cpp\n    vector<int> findClosestElements(vector<int>& arr, int k, int x) {\n        partial_sort(begin(arr), next(begin(arr), k), end(arr), [x](int a, int b) {\n           return abs(a - x) < abs(b - x);\n        });\n        arr.resize(k);\n        sort(begin(arr), end(arr));\n        return arr;\n    }\n```\n\nLooking at the reference for ```std::partial_sort```: "The order of equal elements is not guaranteed to be preserved." made me realize that this approach potentially has the same problem as my frist attempt to use ```std::nth_element``` ran into, i.e. we need to make sure that for elements with the same distance to ```x``` we need to pick the smaller one. This would be fixed by using the same compare function as the next approach. I guess reading the problem description carefully helps. :) \n\n### Approach 3: nth_element, resize, sort\n\nThe post from @PencilBro27 made me realize where my previous approach with using ```nth_element``` instead of ```partial_sort``` failed. For elements that have the same distance to ```x``` we need to pick the smaller one. What\'s nice about this approach is that we don\'t care about the order of elements when we are selecting them as we sort again anyway.\n\n```cpp\n   vector<int> findClosestElements(vector<int>& arr, int k, int x) {\n        nth_element(begin(arr), next(begin(arr), k - 1), end(arr), [x](int a, int b) {\n            const int ad = abs(a - x);\n            const int bd = abs(b - x);\n            return ad != bd ? ad < bd : a < b;\n        });\n        arr.resize(k);\n        sort(begin(arr), end(arr));\n        return arr;\n    }\n```\n\n### Approach 4: binary search\n\nThis is very similar to a LC solution. Slighlty more natural would be to use ```int``` indexes into the array, but I just felt like using iterators. :)\n\n```cpp\n    vector<int> findClosestElements(vector<int>& arr, int k, int x) {\n        auto lo = begin(arr);\n        auto hi = prev(end(arr), k);\n        \n        while (lo < hi) {\n            auto mid = lo + (hi - lo) / 2;\n            if (x - *mid > *next(mid, k) - x) {\n                lo = next(mid);\n            } else {\n                hi = mid;\n            }\n        }\n        \n        vector<int> ans;\n        ans.reserve(k);\n        copy(lo, next(lo, k), back_inserter(ans));\n        return ans;\n    }\n```\n\n### Approach 5: two pointers, narrow from left and right\n\nThis is inspired by a post from @amansingh11. As with the solution above it might be simpler to use ```int``` indexes instead of iterators.\n\n```cpp\n    vector<int> findClosestElements(vector<int>& arr, int k, int x) {\n        auto lo = begin(arr);\n        auto hi = prev(end(arr));\n        \n        while (distance(lo, hi) >= k) {\n            if (abs(*lo - x) > abs(*hi - x)) {\n                ++lo;\n            } else {\n                --hi;\n            }\n        }\n       \n        vector<int> ans;\n        ans.reserve(k);\n        copy(lo, next(hi), back_inserter(ans));\n        return ans;\n    }\n```\n\n### Approach 6: priority queue\n\nAs with many of the "closest k" problems, a priority queue can be used as well to solve them.\n\n```cpp\n   vector<int> findClosestElements(vector<int>& arr, int k, int x) {\n       auto cmp = [x](int a, int b) {\n            const int ad = abs(a - x);\n            const int bd = abs(b - x);\n            return ad != bd ? ad < bd : a < b;\n       };\n       priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);\n       for (int a : arr) {\n           if (size(pq) < k || cmp(a, pq.top())) {\n               pq.push(a);\n               if (size(pq) > k) pq.pop();\n           }\n       }\n       vector<int> ans;\n       ans.reserve(k);\n       while (!empty(pq)) {\n           ans.push_back(pq.top());\n           pq.pop();\n       }\n       sort(begin(ans), end(ans));\n       return ans;\n    }\n```\n\n\n_As always: Feedback, question, and comments are welcome. ... and leave a like before you leave. :)_\n\n**p.s. Join us on the [LeetCode The Hard Way Discord Server](https://discord.gg/Nqm4jJcyBf)!**
['C']