Problem:
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 \(10^4\)
Absolute value of elements in the array and x will not exceed \(10^4\)
思路:
Solution (C++):
struct Comp {
bool operator()(int a, int b) {
if (abs(a) != abs(b)) return abs(a) > abs(b);
return a > b;
}
};
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
for (int i = 0; i < arr.size(); ++i) arr[i] -= x;
priority_queue<int, vector<int>, Comp> que;
vector<int> res;
for (auto n : arr) que.emplace(n);
while (k-- && !que.empty()) {
res.push_back(que.top() + x);
que.pop();
}
sort(res.begin(), res.end());
return res;
}
性能:
Runtime: 388 ms Memory Usage: 14 MB
思路:
Solution (C++):
性能:
Runtime: ms Memory Usage: MB
原文链接: https://www.cnblogs.com/dysjtu1995/p/12729229.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/342910
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!