If I were the interviewer


  • 0
    B

    If I were the interviewer, I want to see you use binary search find the position where you can insert x, and then expand two direction to search for closest k element to put them into result.
    I think I just don't get it. Why after using binarySearch, a subList method is suffice to fulfill the question?? (Below is my solution)

    class Solution {
        int binarySearch(List<Integer> A, int x) {
            int b = 0;
            int e = A.size();
            while (b < e) {
                int m = b + (e-b)/2;
                if (A.get(m) < x) {
                    b = m+1;
                } else {
                    e = m;
                }
            }
            return b;
        }
        public List<Integer> findClosestElements(List<Integer> arr, int k, int x) {
            int index = binarySearch(arr, x);
            List<Integer> res = new ArrayList<>();
            int left = index-1;
            int right = index;
            while (res.size() < k) {
                if (left >= 0 && right < arr.size()) {
                    if (arr.get(right)-x < x-arr.get(left)) {
                        res.add(arr.get(right));
                        right ++;
                    } else {
                        res.add(0, arr.get(left));
                        left --;
                    }
                } else if (left < 0 && right < arr.size()) {
                    res.add(arr.get(right));
                    right++;
                } else if (left >= 0 && right >= arr.size()) {
                    res.add(0, arr.get(left));
                    left--;
                } else {
                    break;
                }
            }
            return res;
        }
    }
    

Log in to reply
 

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