Uber 电面

感觉这题可以直接用lambda把x附近2k长度的window里的数按照跟x的差值排个序。因为数组本身已经排好序了，所以排序本身基本也是linear的。

LC上通过的代码，速度64%

1.     vector<int> findClosestElements(vector<int>& arr, int k, int x) {
   
2.         size_t headIdx = max(int(lower_bound(arr.begin(), arr.end(), x) - arr.begin()) - k, 0);
   
3.         size_t tailIdx = min(int(upper_bound(arr.begin(), arr.end(), x) - arr.begin()) + k, int(arr.size() - 1));
   
4.         vector<int> window(arr.begin() + headIdx, arr.begin() + tailIdx + 1);  //window是arr里在x两边k距离以内的数
   
5.         sort(window.begin(), window.end(), [x](int a, int b) {
   
6.             return (abs(a-x) < abs(b-x) || (abs(a-x) == abs(b-x) && a < b));
   
7.         });
   
8.         window.resize(k); //
   
9.         sort(window.begin(), window.begin() + k);
   
10.         return window;
    
11.     }

复制代码

补充内容 (2017-12-13 15:22):
想了一下不对，要用排序的话，最后有要求按顺序输出k个idx，还得拍次序。

参考 cnblogs.com/grandyang/p/7519466.html