Java O(n) two pointers, very very simple


  • 0
    N

    A simple solution:

    Start with two pointers -- left and right, which point to the two ends of the list, respectively.

    Given the question assumption, we know initially right - left + 1 > k for sure.
    In order to get the sublist with length k, we need move either right pointer or left pointer towards each other, the moving rule is following:

    if abs(left - x) <= abs(right - x)
        move right pointer towards left
    else 
        move left pointer towards right
    

    Very simple, agree?

    Here is the complete java code:

    class Solution {
        public List<Integer> findClosestElements(List<Integer> arr, int k, int x) {
            
            int left = 0;
            int right = arr.size() - 1;
            
            while (right - left + 1 > k) {
                
                int ld = Math.abs(arr.get(left) - x);
                int rd = Math.abs(arr.get(right) - x);
    
                if (ld <= rd) {
                    right --;
                } else {
                    left ++;
                }
            }
            return arr.subList(left, right + 1);
        }
        
    }
    

Log in to reply
 

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