A Java O(lgn + k) Solution


  • 0
    M

    The runtime beats 72.16 % of java submissions.

    class Solution {
        private List<Integer> appendK(List<Integer> arr, int start, int end, int x, int k) {
            List<Integer> res = new ArrayList<>();
            int cloest = Math.abs(x - arr.get(start)) <= Math.abs(x - arr.get(end)) ? start : end;
            if (k == 1) {
                res.add(arr.get(cloest));
                return res;
            }
            start = cloest;
            end = cloest;
            while (end - start < k - 1) {
                if (start == 0) {
                    end++;
                } else if (end == arr.size() - 1) {
                    start--;
                } else {
                    int dist1 = Math.abs(x - arr.get(start - 1));
                    int dist2 = Math.abs(x - arr.get(end + 1));
                    if (dist1 <= dist2 ) {
                        start--;
                    } else {
                        end++;
                    }
                }
            }
            
            for (int i = start; i <= end; i++) {
                res.add(arr.get(i));
            }
            
            return res;
        }
        
        public List<Integer> findClosestElements(List<Integer> arr, int k, int x) {
            int start = 0, end = arr.size() - 1;
            while (start + 1 < end) {
                int mid = start + (end - start) / 2;
                if (arr.get(mid) == x) {
                    end = mid;
                } else if (arr.get(mid) < x) {
                    start = mid;
                } else {
                    end = mid;
                }
            }
            
            List<Integer> res = appendK(arr, start, end, x, k);
            
            return res;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.