讨论/《二分查找》 - 找到 K 个最接近的元素/
《二分查找》 - 找到 K 个最接近的元素

附上一个傻办法

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        List<Integer> res = new ArrayList<>();
        int index = binSearch(arr, x);
        if(index == -1 || index == 0){
            for(int i = 0 ; i<k;i++){
                res.add(arr[i]);
            }
        }else{
            int left = index, right = index+1;
            while(res.size() < k){
                if(left>=0 && right < arr.length){
                    if(Math.abs(arr[left] - x) <= Math.abs(arr[right] - x)){
                        res.add(arr[left]);
                        left--;
                    }else{
                        res.add(arr[right]);
                        right++;
                    }
                }else if(left < 0){
                    res.add(arr[right]);
                    right++;
                }else if(right == arr.length){
                    res.add(arr[left]);
                    left--;
                }              
            }
        }
        Collections.sort(res);
       return res;
    }

    public int binSearch(int[] arr, int x){
        if(x< arr[0])return -1;
        int left = 0, right = arr.length-1;
         while(left +1 < right){
            int mid = left + (right - left)/2;
            if(x == arr[mid]){
                return mid;
            }else if(x < arr[mid]){
                right = mid;
            }else{
                left = mid;
            }
        }
        if(Math.abs(arr[left] - x) <= Math.abs(arr[right] - x))
            return left;
        return right;
        
    }
}
展开全部 7 讨论