Deque TIME O(N) SPACE O(N)


  • 0
    class Solution {
        public List<Integer> findClosestElements(List<Integer> arr, int k, int x) {
            List<Integer> res = new ArrayList<>();
            int idx = Collections.binarySearch(arr, x);
            Deque<Integer> deque = new LinkedList<>();
            int bigIdx = 0;
            int smlIdx = 0;
            if (idx >= 0) {
                deque.offer(arr.get(idx));
                bigIdx = idx + 1;
                smlIdx = idx - 1;
                k--;
            } else {
                idx = - (idx + 1);
                bigIdx = idx;
                smlIdx = idx - 1;
            }
            while (k > 0 && (bigIdx < arr.size() || smlIdx >= 0)) {
                if (bigIdx < arr.size() && (smlIdx < 0 || arr.get(bigIdx)- x < x - arr.get(smlIdx))) {
                    deque.offerLast(arr.get(bigIdx));
                    bigIdx++;
                    k--;
                } else if(smlIdx >= 0 && (bigIdx >= arr.size() || arr.get(bigIdx)- x >= x - arr.get(smlIdx))) {
                    deque.offerFirst(arr.get(smlIdx));
                    smlIdx--;
                    k--;
                }
            }
            for (Integer inter : deque) {
                res.add(inter);
            }
            return res;
        }
    }
    

Log in to reply
 

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