題目

給定一個(gè)排序好的數(shù)組，從數(shù)組中找到最靠近x（兩數(shù)之差最锌住）的k個(gè)數(shù)。
返回的結(jié)果必須要是按升序排好的宝鼓。
如果有兩個(gè)數(shù)與x的差值一樣刑棵，優(yōu)先選擇數(shù)值較小的那個(gè)數(shù)。
例如：
[1,2,3,4,5], k=4, x=3 結(jié)果是：[1,2,3,4]
[1,2,3,4,5], k=4, x=-1 結(jié)果是：[1,2,3,4]

解析

第一種O(n)時(shí)間復(fù)雜度方法

依次遍歷有序數(shù)組A愚铡，計(jì)算每個(gè)數(shù)組元素與x的絕對(duì)值铐望，找到最接近x的那個(gè)數(shù)值。然后以這個(gè)數(shù)值中心向兩端展開，直到展開的窗口大小是k為止正蛙。

第二種O(lgn)時(shí)間復(fù)雜度方法

在第一種方法基礎(chǔ)上進(jìn)行改進(jìn)督弓，在查找最接近x的那個(gè)數(shù)值不再依次遍歷，而是使用二分查找的方法乒验，節(jié)約查找的時(shí)間愚隧。

代碼

public List<Integer> findClosestElements(int[] arr, int k, int x) {
    List<Integer> res = new LinkedList<>();
    //如果數(shù)組個(gè)數(shù)小于等于k，直接返回
    if(arr.length <= k){
        for(int i=0; i<arr.length; i++){
            res.add(arr[i]);
        }
        return res;
    }
    //調(diào)用二分查找函數(shù)找到最接近x的數(shù)值下標(biāo)
    int midIndex = findClosestIndex(arr, x, 0, arr.length - 1);
    //已經(jīng)找到一個(gè)最接近x的值了
    int total = 1;
    if(total == k){
        res.add(arr[midIndex]);
        return res;
    }
    //窗口前后移動(dòng)的下標(biāo)
    int i = midIndex - 1;
    int j = midIndex + 1;
    //展開窗口锻全，保證兩個(gè)下標(biāo)不全部越界
    while(i >= 0 || j <= (arr.length - 1)){
        //如果兩個(gè)下標(biāo)都在界限范圍內(nèi)
        if(i >= 0 && j <= (arr.length - 1)){
            //選擇接近的元素狂塘，擴(kuò)大窗口
            if(Math.abs(arr[i] - x) <= Math.abs(arr[j] - x)){
                i--;
            } else {
                j++;
            }
        } else if(i < 0){//前面的下標(biāo)越界，向后擴(kuò)大窗口
            j++;
        } else if (j > (arr.length - 1)){//后面的下標(biāo)越界鳄厌，向前擴(kuò)大窗口
            i--;
        }
        //每次總數(shù)加1
        total++;
        //如果已經(jīng)符合k個(gè)數(shù)組荞胡，結(jié)束尋找
        if(total == k){
            break;
        }
    }
    //結(jié)果存入鏈表中
    for(i = i + 1; i < j; i++){
        res.add(arr[i]);
    }
    return res;
}

//二分查找，找到最接近x的那個(gè)數(shù)值
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了嚎，直接返回下標(biāo)
        if(arr[index] == x){
            return index;
        } else if(arr[index] < x){
            s = index + 1;
        } else {
            e = index - 1;
        }
    }
    //如果未查找到下標(biāo)
    int index;
    //如果前面的指針超過數(shù)組上界泪漂，返回尾指針的下標(biāo)
    if(s > arr.length - 1){
        index = e;
    } else if(e < 0){//如果尾指針超出數(shù)組下界，返回頭指針下標(biāo)
        index = s;
    } else {//如果首尾指針都沒有越界歪泳，比較s和e所在元素與x的絕對(duì)值萝勤，返回結(jié)果小的那個(gè)
        if(Math.abs(x - arr[s]) >= Math.abs(x - arr[e])){
            index = e;
        } else {
            index = s;
        }
    }
    return index;
}