找到 K 个最接近的元素(LeetCode658.找到 K 个最

题目

给定一个排序好的数组，从数组中找到最靠近x（两数之差最小）的k个数。
返回的结果必须要是按升序排好的。
如果有两个数与x的差值一样，优先选择数值较小的那个数。
例如：
[1,2,3,4,5], k=4, x=3 结果是：[1,2,3,4]
[1,2,3,4,5], k=4, x=-1 结果是：[1,2,3,4]

解析

第一种O(n)时间复杂度方法

依次遍历有序数组A，计算每个数组元素与x的绝对值，找到最接近x的那个数值。然后以这个数值中心向两端展开，直到展开的窗口大小是k为止。

第二种O(lgn)时间复杂度方法

在第一种方法基础上进行改进，在查找最接近x的那个数值不再依次遍历，而是使用二分查找的方法，节约查找的时间。

代码

public List<Integer> findClosestElements(int[] arr, int k, int x) {
    List<Integer> res = new LinkedList<>();
    //如果数组个数小于等于k，直接返回
    if(arr.length <= k){
        for(int i=0; i<arr.length; i++){
            res.add(arr[i]);
        }
        return res;
    }
    //调用二分查找函数找到最接近x的数值下标
    int midIndex = findClosestIndex(arr, x, 0, arr.length - 1);
    //已经找到一个最接近x的值了
    int total = 1;
    if(total == k){
        res.add(arr[midIndex]);
        return res;
    }
    //窗口前后移动的下标
    int i = midIndex - 1;
    int j = midIndex + 1;
    //展开窗口，保证两个下标不全部越界
    while(i >= 0 || j <= (arr.length - 1)){
        //如果两个下标都在界限范围内
        if(i >= 0 && j <= (arr.length - 1)){
            //选择接近的元素，扩大窗口
            if(Math.abs(arr[i] - x) <= Math.abs(arr[j] - x)){
                i--;
            } else {
                j++;
            }
        } else if(i < 0){//前面的下标越界，向后扩大窗口
            j++;
        } else if (j > (arr.length - 1)){//后面的下标越界，向前扩大窗口
            i--;
        }
        //每次总数加1
        total++;
        //如果已经符合k个数组，结束寻找
        if(total == k){
            break;
        }
    }
    //结果存入链表中
    for(i = i + 1; i < j; i++){
        res.add(arr[i]);
    }
    return res;
}

//二分查找，找到最接近x的那个数值
private int findClosestIndex(int[] arr, int x, int start, int end){
    int s = start, e = end;
    //二分查找
    while(s <= e){
        int index = (s + e) / 2;
        //查找到x，直接返回下标
        if(arr[index] == x){
            return index;
        } else if(arr[index] < x){
            s = index + 1;
        } else {
            e = index - 1;
        }
    }
    //如果未查找到下标
    int index;
    //如果前面的指针超过数组上界，返回尾指针的下标
    if(s > arr.length - 1){
        index = e;
    } else if(e < 0){//如果尾指针超出数组下界，返回头指针下标
        index = s;
    } else {//如果首尾指针都没有越界，比较s和e所在元素与x的绝对值，返回结果小的那个
        if(Math.abs(x - arr[s]) >= Math.abs(x - arr[e])){
            index = e;
        } else {
            index = s;
        }
    }
    return index;
}