1. 代码段小站首页
  2. 算法

leetcode658-找到K个最接近的元素

彭晨涛 • • 算法 • 阅读 11

原题

给定一个排序好的数组，两个整数 k 和 x，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。如果有两个数与 x 的差值一样，优先选择数值较小的那个数。

示例1：

输入: [1,2,3,4,5], k=4, x=3
输出: [1,2,3,4]

示例2：

输入: [1,2,3,4,5], k=4, x=-1
输出: [1,2,3,4]

说明:

  1. k 的值为正数，且总是小于给定排序数组的长度。
  2. 数组不为空，且长度不超过 104
  3. 数组里的每个元素与 x 的绝对值不超过 104

解法

思想

  1. 按照差值排序
  2. 双指针

代码

  1. 排序
public List<Integer> findClosestElements(List<Integer> arr, int k, int x) {
     Collections.sort(arr, (a,b) -> a == b ? a - b : Math.abs(a-x) - Math.abs(b-x));
     arr = arr.subList(0, k);
     Collections.sort(arr);
     return arr;
}
  1. 双指针（作者：liweiwei1419）
public class Solution {

    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int size = arr.length;

        int left = 0;
        int right = size - 1;

        int removeNums = size - k;
        while (removeNums > 0) {
            if (x - arr[left] <= arr[right] - x) {
                right--;
            } else {
                left++;
            }
            removeNums--;
        }

        List<Integer> res = new ArrayList<>();
        for (int i = left; i < left + k; i++) {
            res.add(arr[i]);
        }
        return res;
    }
}

原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode658-%e6%89%be%e5%88%b0k%e4%b8%aa%e6%9c%80%e6%8e%a5%e8%bf%91%e7%9a%84%e5%85%83%e7%b4%a0/

赞 (0)
彭晨涛彭晨涛管理者
0 0
上一篇 2020年1月3日 17:58
下一篇 2020年1月4日 20:54

相关推荐

发表回复

登录后才能评论