题目描述
给定一个排序好的数组，两个整数 k 和 x，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。如果有两个数与 x 的差值一样，优先选择数值较小的那个数。
示例1
输入： [1,2,3,4,5], k=4, x=3 输出： [1,2,3,4]
示例2
输入： [1,2,3,4,5], k=4, x=-1 输出： [1,2,3,4]
提示
- k 的值为正数，且总是小于给定排序数组的长度
- 数组不为空，且长度不超过 10^4
- 数组里的每个元素与 x 的绝对值不超过 10^4
题解
滑动窗口
二分+滑动窗口
二分
代码
滑动窗口（c++）
classSolution { public: vector<int>findClosestElements(vector<int>&arr, intk, intx) { intn=arr.size(); intl=0, r=n-1; while (r-l>=k) { if (x-arr[l] <=arr[r]-x) r--; elsel++; } vector<int>res(k); copy(arr.begin()+l, arr.begin()+l+k, res.begin()); returnres; } };
二分+滑动窗口（c++）
classSolution { public: vector<int>findClosestElements(vector<int>&arr, intk, intx) { intn=arr.size(); intl=0, r=n-1; while (l<r) { intm= (l+r) /2; if (arr[m] <x) l=m+1; elser=m; } r=min(n-1, l+k-1); l=max(0, l-k); while (r-l>=k) { if (x-arr[l] <=arr[r]-x) r--; elsel++; } vector<int>res(k); copy(arr.begin()+l, arr.begin()+l+k, res.begin() ); returnres; } };
二分（c++）
classSolution { public: vector<int>findClosestElements(vector<int>&arr, intk, intx) { intn=arr.size(); intl=0, r=n-k; while (l<r) { intm= (l+r) /2; if (x-arr[m] >arr[m+k]-x) l=m+1; elser=m; } vector<int>res(k); copy(arr.begin()+l, arr.begin()+l+k, res.begin() ); returnres; } };
滑动窗口（python）
classSolution: deffindClosestElements(self, arr: List[int], k: int, x: int) ->List[int]: n=len(arr) l, r=0, n-1whiler-l>=k: ifx-arr[l] <=arr[r]-x: r-=1else: l+=1returnarr[l:l+k]
二分+滑动窗口（python）
classSolution: deffindClosestElements(self, arr: List[int], k: int, x: int) ->List[int]: n=len(arr) l, r=0, n-1whilel<r: m= (l+r) //2ifarr[m] <x: l=m+1else: r=mr=min(n-1, l+k-1) l=max(0, l-k) whiler-l>=k: ifx-arr[l] <=arr[r]-x: r-=1else: l+=1returnarr[l:l+k]
二分（python）
classSolution: deffindClosestElements(self, arr: List[int], k: int, x: int) ->List[int]: n=len(arr) l, r=0, n-kwhilel<r: m= (l+r) //2ifx-arr[m] >arr[m+k]-x: l=m+1else: r=mreturnarr[l:l+k]
作者简介：godweiyang，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~
