您现在的位置是:首页 >技术杂谈 >Leetcode力扣秋招刷题路-0658网站首页技术杂谈

Leetcode力扣秋招刷题路-0658

fffffffyy 2023-06-13 20:00:02
简介Leetcode力扣秋招刷题路-0658

从0开始的秋招刷题路,记录下所刷每道题的题解,帮助自己回顾总结

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 <= 1 0 4 10^4 104
arr 按 升序 排列
− 1 0 4 -10^4 104 <= arr[i], x <= 1 0 4 10^4 104

方法一:双指针
我们要想找到K个最接近的元素,可以删除n-k的元素来达到目的。 由于数组是有序的,因此最接近的k个元素一定是在数组中连续的,因此我们维护两个左右指针

若x - arr[left] <= arr[right] - x,则移动右指针,否则移动左指针,直到删除n-k个元素

代码如下

public List<Integer> findClosestElements(int[] arr, int k, int x) {
    //数组长度
    int n = arr.length;
    //左右指针
    int left = 0, right = n - 1;
    //要删除的个数
    int delCnt = n - k;
    while (delCnt > 0) {
        if (x - arr[left] <= arr[right] - x) {
            right--;
        } else {
            left++;
        }
        delCnt--;
    }
    //从左到右添加元素
    List<Integer> ans = new ArrayList<>();
    for (int i = left; i < left + k; i++) {
        ans.add(arr[i]);
    }
    return ans;
}
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。