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:
思路：
用一个map记录数组中的值距离x的大小，利用map有序的特性。
int SIZE = arr.size(); map<int, vector<int>> m; for(int i = 0; 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 = 0; 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 = 0; 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 = 0; cur.clear(); for( int i = 0; 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; }
[leetcode-658-Find K Closest Elements]
原文：http://www.cnblogs.com/hellowooorld/p/7352757.html