LeetCode Find K Closest Elements Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred. Example 1:

Input: [1,2,3,4,5], k=4, x=3
Output: [1,2,3,4]

Example 2:

Input: [1,2,3,4,5], k=4, x=-1
Output: [1,2,3,4]

Note:

1. The value k is positive and will always be smaller than the length of the sorted array.
2. Length of the given array is positive and will not exceed 10⁴
3. Absolute value of elements in the array and x will not exceed 10⁴

---

给定一个有序数组，要从中找出k个和x最接近的元素，按升序排列输出。 首先在有序数组中用二分查找找到x的lowerbound，如果lowerbound指向begin()，则取开头k个元素即可；如果lowerbound指向end()，则取末尾k个元素；否则，令left指向lowerbound-1，right指向lowerbound，每次取left、right中和x差值最小的那个数，直到取够k个为止。最后对结果数组排序。 完整代码如下： [cpp] class Solution { public: vector<int> findClosestElements(vector<int>& arr, int k, int x) { vector<int> ans; int n = arr.size(); auto it = lower_bound(arr.begin(), arr.end(), x); if (it == arr.begin()) { while (ans.size() < k) { ans.push_back(*it++); } return ans; } else if (it == arr.end()) { while (ans.size() < k) { ans.push_back(*–it); } return ans; } else { int right = it – arr.begin(); int left = right – 1; int left_diff = INT_MAX, right_diff = INT_MAX; while (ans.size() < k) { if (left >= 0)left_diff = abs(arr[left] – x); else left_diff = INT_MAX; if (right < n)right_diff = abs(arr[right] – x); else right_diff = INT_MAX; if (left_diff <= right_diff) { ans.push_back(arr[left]); –left; } else { ans.push_back(arr[right]); ++right; } } } sort(ans.begin(), ans.end()); return ans; } }; [/cpp] 本代码提交AC，用时143MS。]]>