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:
- The value k is positive and will always be smaller than the length of the sorted array.
- Length of the given array is positive and will not exceed 104
- Absolute value of elements in the array and x will not exceed 104
思路:
用一个map记录数组中的值距离x的大小,利用map有序的特性。
int SIZE = arr.size();
map<int, vector<int>> m;
for(int i = ; i < SIZE; ++i) {
int val = arr[i];
m[abs(val - x)].push_back(val);
}
vector<int> ans;
auto it = m.begin();
while(ans.size() < k) {
vector<int> &v = it->second;
sort(v.begin(), v.end());
int i = ;
while(i < v.size() && k > ans.size()) {
ans.push_back(v[i++]);
}
++it;
}
sort(ans.begin(), ans.end());
return ans;
vector<int> findClosestElements(vector<int>& arr, int k, int x)
{
vector< int > ret;
vector< int > cur;
auto it = lower_bound( arr.begin(), arr.end(), x );//低
//cout << *it << endl; long long sum = ;
long long min_val = 0xc0c0c0c0;
auto it_start = ( it - k < arr.begin() ) ? arr.begin() : it-k;
auto it_end = ( it > arr.end() - k ) ? arr.end() - k : it; //cout << *it_start << endl;
//cout << *it_end << endl; for( auto it_cur = it_start; it_cur <= it_end; it_cur++ )
{
sum = ;
cur.clear();
for( int i = ; i < k; i++ )
{
cur.push_back( *(it_cur+i) );
sum += abs( ( *(it_cur+i) - x ) );
}
if( sum < min_val )
{
min_val = sum;
swap( ret, cur );
}
} return ret;
}