658. Find K Closest Elements

Given a sorted array, two integerskandx, find thekclosest elements toxin the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.

Example 1:

Input:
 [1,2,3,4,5], k=4, x=3

Output:
 [1,2,3,4]

Example 2:

Input:
 [1,2,3,4,5], k=4, x=-1

Output:
 [1,2,3,4]

Note:

1. The value k is positive and will always be smaller than the length of the sorted array.

2. Length of the given array is positive and will not exceed 10^4

3. Absolute value of elements in the array and x will not exceed 10^4

Thoughts:

1. Binary -searching the first index i that arr[i] is closer or equally close to arr[i+k] (Original Post)

2. Binary-searching forxand then expanding to the left and to the right: The idea is to find the first number which is equal to or greater thanxinarr. Then, we determine the indices of the start and the end of a subarray inarr, where the subarray is our result. The time complexity is O(logn + k)

   .

Code: Binary -searching for the first index i T: O(log(n-k))

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int i = 0, j = arr.length - k;
        while (i < j){
            int mid = (i & j) + ((i ^ j) >> 1);
            // int mid = i + (j - i >> 1);
            if(x - arr[mid] > arr[mid + k] - x)
                i = mid + 1;
            else
                j = mid;
        }
        List<Integer> res = new ArrayList<>();
        for (int b = i; b < i + k; ++b) res.add(arr[b]);
        return res;
        // return Arrays.stream(Arrays.copyOfRange(arr, i, i + k)).boxed().collect(Collectors.toList()); 

    }
}

Python: T: O(log(n-k))

class Solution(object):
    def findClosestElements(self, arr, k, x):
        """
        :type arr: List[int]
        :type k: int
        :type x: int
        :rtype: List[int]
        """
        i, j = 0, len(arr) - k
        while i < j:
            mid = (i & j) + ((i^j)>> 1)
            if x - arr[mid] > arr[mid + k] - x: # arr is sorted
                i = mid + 1
            else:
                j = mid

        return arr[i:i+k]

Code 2: Reference T: O(log(n)+k)

  public List<Integer> findClosestElements(List<Integer> arr, int k, int x) {
        int index = Collections.binarySearch(arr, x);
        if(index < 0) index = -(index + 1);
        int i = index - 1, j = index;                                    
        while(k-- > 0){
            if(i < 0 || (j < arr.size() && Math.abs(arr.get(i) - x) > Math.abs(arr.get(j) - x)))j++;
            else i--;
        }
        return arr.subList(i+1, j);
    }