class Solution {
public:
int get(vector<int>& arr,int left,int right,int x)
{
int ret = 0;
for(int i=left;i<=right;i++)
{
ret+=abs(arr[i]-x);
}
return ret;
}
vector<int> findClosestElements(vector<int>& arr, int k, int x)
{
if(k==1)
{
vector<int> ret;
int retvalue = INT_MAX;
for(int i=0;i<arr.size();i++)
{
if(arr[i]==x)
return {arr[i]};
if(retvalue>abs(arr[i]-x))
{
ret.clear();
retvalue = abs(arr[i]-x);
ret.push_back(arr[i]);
}
}
return ret;
}
vector<int> ret;
int left = 0;
int right = k-1;
int value = INT_MAX;
int ileft = 0;
int iright = k-1;
while(right<arr.size())
{
if(value>get(arr,left,right,x))
{
ileft = left;
iright = right;
value = get(arr,left,right,x);
}
right++;
left++;
}
for(int i=ileft;i<=iright;i++)
ret.push_back(arr[i]);
return ret;
}
};
个人做法,非最优解
官解:
class Solution {
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
sort(arr.begin(), arr.end(), [x](int a, int b) -> bool {
return abs(a - x) < abs(b - x) || (abs(a - x) == abs(b - x) && a < b);
});
sort(arr.begin(), arr.begin() + k);
return vector<int>(arr.begin(), arr.begin() + k);
}
};