658-find-k-closest-elements.md

658. Find K Closest Elements - 找到 K 个最接近的元素

给定一个排序好的数组，两个整数 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. 数组不为空，且长度不超过 10⁴
3. 数组里的每个元素与 x 的绝对值不超过 10⁴

 

更新(2017/9/19):
这个参数 arr 已经被改变为一个整数数组（而不是整数列表）。 请重新加载代码定义以获取最新更改。

---

题目标签：Binary Search

题目链接：LeetCode / LeetCode中国

题解

Language	Runtime	Memory
java	23 ms	41.2 MB

class Solution {
    class Node {
        int value;
        int interval;
        Node(int value, int interval) {
            this.value = value;
            this.interval = interval;
        }
    }

    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        Node[] nds = new Node[arr.length];
        for (int i = 0; i < arr.length; i++) {
            nds[i] = new Node(arr[i], Math.abs(arr[i] - x));
        }
        Arrays.sort(nds, new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o1.interval == o2.interval ? o1.value - o2.value : o1.interval - o2.interval;
            }
        });
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            res.add(nds[i].value);
        }
        res.sort(null);
        return res;
    }
}