题目简介：
给定一个 排序好 的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。
整数 a 比整数 b 更接近 x 需要满足：
|a - x| == |b - x| 且 a < b
示例 1：
1
2
| 输入：arr = [1,2,3,4,5], k = 4, x = 3
输出：[1,2,3,4]
|
提示：
1 <= k <= arr.length1 <= arr.length <= 104arr 按 升序 排列-104 <= arr[i], x <= 104
思路：
利用优先队列，将每个元素与x差值的绝对值压入队列，每次top()操作返回的都是队列中绝对值最大的元素(即隔的最远的元素)。
因此，我们只需要控制队列的大小即可。
tip:
- 这题可以直接按照差值的绝对值进行排序，更方便…只是一开始做的时候没想到。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| class Solution {
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
priority_queue<pair<int, int>> qu;
for(int i = 0; i < arr.size(); i++){
if(qu.size() < k){
qu.push(make_pair(abs(x - arr[i]), arr[i]));
continue;
}
auto top_item = qu.top();
if(abs(x - arr[i]) < top_item.first){
qu.push(make_pair(abs(x - arr[i]), arr[i]));
qu.pop();
}
}
vector<int> res;
while(!qu.empty()){
res.push_back(qu.top().second);
qu.pop();
}
sort(res.begin(), res.end());
return res;
}
};
|
