力扣：658. 找到 K 个最接近的元素

携手创作，共同成长！这是我参加「日新方案 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;
    }
};