携手创作,共同成长!这是我参加「日新方案 8 月更文挑战」的第27天,点击检查活动详情
658. 找到 K 个最挨近的元素
给定一个 排序好 的数组arr ,两个整数 k 和 x ,从数组中找到最靠近 x(两数之差最小)的 k 个数。回来的成果必须要是按升序排好的。
整数 a 比整数 b 更挨近 x 需要满足:
- |a – x| < |b – x| 或许
- |a – x| == |b – x| 且 a < b
示例 1:
输入:arr = [1,2,3,4,5], k = 4, x = 3
输出:[1,2,3,4]
示例 2:
输入:arr = [1,2,3,4,5], k = 4, x = -1
输出:[1,2,3,4]
提示:
- 1 <= k <= arr.length
- 1 <= arr.length<= 104
- arr按 升序 排列
- -104<= arr[i], x <= 104
问题解析
自定义排序
咱们能够想办法,把最挨近x的数都挪放到数组的前面来,这样最前面的k个数便是咱们要的答案了。
能够用自定义排序规则cmp来实现这一过程,关于数组arr中的两个数a,b来说:
- 假如abs(x-a)<abs(x-b),那咱们能够把数字a放到b的前面,因为a显然比b更挨近x。
- 假如abs(x-a)==abs(x-b),那咱们把a和b中两者较小的部分放在前面。
(其实能够看出,这其实便是标题给的两个条件)
依照自定义排序对arr数组排序后,咱们直接取出前面的k个元素即可。
要注意的是,标题要回来的是升序序列,而自定义排序可能会把顺序搞混,所以咱们还要对成果排序后再回来。
AC代码
int num;
bool cmp(int a,int b)
{
int x=abs(a-num),y=abs(b-num);
if(x!=y)return x<y;
return a<b;
}
class Solution {
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
num=x;
sort(arr.begin(),arr.end(),cmp);
vector<int>res;
for(int i=0;i<k;i++)res.push_back(arr[i]);
return res;
}
};