658. Find K Closest Elements

2019-02-18  本文已影响0人  AThornBird
class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        if (k == 0) {
             List<Integer> list = new ArrayList<Integer>();
             // list.add(0);
             return list;
        }
        
        int left = largestSmallerEqual(arr, x);
        int right = left + 1;
        int start = 0;
        int end = 0;
        List<Integer> result = new ArrayList<>(); 
        
        for(int i = 0; i < k ; i++) {       
            if(right >= arr.length || left >= 0 && Math.abs(x - arr[left]) <= Math.abs(arr[right] - x)) {
                start = left--;
            } else {
                end = right++;
            }
        }
        
        for(int j = start; j <= start + k - 1; j++) {
            result.add(arr[j]);
        }

        return result;
    }
    
    private int largestSmallerEqual(int[] arr, int x) {
        int left = 0;
        int right = arr.length - 1;
        while (left < right - 1) {
            int mid = left + (right - left) / 2;
            if (arr[mid] <= x) {
                left = mid;
            } else {
                right = mid;
            }
        }
        if (arr[right] <= x){
            return right;
        }
        if (arr[left] <= x) {
            return left;
        }
        return 0;        
    }
}
上一篇下一篇

猜你喜欢

热点阅读