侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【排序, 双指针】找到 K 个最接近的元素

GabrielxD
2022-08-25 / 0 评论 / 0 点赞 / 41 阅读 / 711 字 / 正在检测是否收录...

题目

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


给定一个 排序好 的数组 arr ,两个整数 kx ,从数组中找到最靠近 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 <= 10^4
  • arr 按 升序 排列
  • -10^4 <= arr[i], x <= 10^4

解题

方法一:排序

思路

首先把数组按照与 x 的距离越近越靠前的顺序排序,具体来说:

  • 如果 arr[i]x|arr[i] - x| 相等,越小的越靠前。
  • 否则 arr[i]x|arr[i] - x| 的值越小越靠前。

然后拿出 arr 中前 k 个元素组成一个新的数组后升序排序返回。

代码

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        sort(arr.begin(), arr.end(), [x](int& a, int& b) {
            int diff_a = abs(a - x), diff_b = abs(b - x);
            return diff_a == diff_b ? a < b : diff_a < diff_b;
        });
        sort(arr.begin(), arr.begin() + k);
        return {arr.begin(), arr.begin() + k};
    }
};
class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        List<Integer> lst = new ArrayList<Integer>() {{
            for (int num : arr) this.add(num);
        }};
        Collections.sort(lst, (a, b) -> {
            int diffA = Math.abs(a - x), diffB = Math.abs(b - x);
            return diffA == diffB ? a - b : diffA - diffB;
        });
        List<Integer> ans = lst.subList(0, k);
        Collections.sort(ans);
        return ans;
    }
}

方法二:双指针

思路

反向思考,从排序好的数组 arr 中找到最靠近 xk 个数就是**删除最远离 xarr.length - k**个数。

维护两个指针(left, right)分别指向数组左右两边,如果左指针指向的数与 x 的差值比右指针指向的数与 x 的差值大,说明左边更远离 x 把左指针右移表示删除左边的一个数,反之把右指针左移。

最后返回 arr[left:right+1] (这里类似 python 的数组切片,表示 arr 中的 [left, right+1) 区间)。

代码

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int excld = arr.size() - k;
        auto left = arr.begin(), right = arr.end() - 1;
        for (int i = 0; i < excld; ++i) {
            if (x - *left > *right - x) ++left;
            else --right;
        }
        return {left, right + 1};
    }
};
class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int left = 0, right = arr.length - 1;
        int excld = arr.length - k;
        while (excld-- > 0) {
            if (x - arr[left] > arr[right] - x) ++left;
            else --right;
        }
        List<Integer> ans = new ArrayList<>();
        for (; left <= right; ++left) ans.add(arr[left]);
        return ans;
    }
}
0

评论区