給定一個(gè)排序好的數(shù)組碟绑，兩個(gè)整數(shù) k 和 x剖膳，從數(shù)組中找到最靠近 x（兩數(shù)之差最信撞）的 k 個(gè)數(shù)格侯。返回的結(jié)果必須要是按升序排好的。如果有兩個(gè)數(shù)與 x 的差值一樣财著，優(yōu)先選擇數(shù)值較小的那個(gè)數(shù)联四。
示例 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 的值為正數(shù)，且總是小于給定排序數(shù)組的長度撑教。
數(shù)組不為空朝墩，且長度不超過 104
數(shù)組里的每個(gè)元素與 x 的絕對值不超過 104
更新(2017/9/19):
這個(gè)參數(shù) arr 已經(jīng)被改變?yōu)橐粋€(gè)整數(shù)數(shù)組（而不是整數(shù)列表）。 請重新加載代碼定義以獲取最新更改伟姐。
C++1
解題思路：
使用二分法收苏，使得兩邊都逐漸接近x，但是每次下標(biāo)只會從start增大愤兵，保證如果有兩個(gè)數(shù)與 x 的差值一樣鹿霸，優(yōu)先選擇數(shù)值較小的那個(gè)，也就是左邊的數(shù)秆乳。
class Solution {
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
int size = arr.size();
// 這個(gè)點(diǎn)要選在倒數(shù)第k個(gè)懦鼠，因?yàn)槠鹗键c(diǎn)不可能在這個(gè)或者以后，否則end-begin<k找不到k個(gè)數(shù)了，還有一方面是因?yàn)橄旅嬉胢id+k判斷葛闷，否則程序溢出
int begin = 0, end = size-k, mid=0;
while(begin<end){
mid = begin+(end-begin)/2;
if(abs(arr[mid]-x)>abs(arr[mid+k]-x)){
begin = mid+1;
}else{
end = mid;
}
}
vector<int> res;
for(int i=begin;i<begin+k;i++){
res.push_back(arr[i]);
}
return res;
}
};
C++2
解題思路：
從兩邊向中間縮小范圍憋槐，直到還剩下k個(gè)數(shù)為止。
class Solution {
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
int size = arr.size();
int begin = 0, end = size-1;
while(size>k){
// 這個(gè)等于號不要忘了淑趾，當(dāng)?shù)扔诘臅r(shí)候要選擇保留左邊的數(shù)
if(abs(arr[end]-x)>=abs(arr[begin]-x)){
end--;
}else{
begin++;
}
size--;
}
vector<int>res;
for (int index = begin; index <=end; index++)
res.push_back(arr[index]);
return res;
}
};
