658. Find K Closest Elements (M)

Given a sorted integer array arr, two integers k and x, return the k closest integers to x in the array. The result should also be sorted in ascending order.

An integer a is closer to x than an integer b if:

• |a - x| < |b - x|, or

• |a - x| == |b - x| and a < b

Example 1:

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

Example 2:

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

Constraints:

• 1 <= k <= arr.length

• 1 <= arr.length <= 104

• arr is sorted in ascending order.

• -104 <= arr[i], x <= 104

Solution:

直接在数组中二分查找 target, 如果不存在则返回大于 target 的最小的或者小于 target 的最大的元素均可.

然后使用两根指针从该位置开始向两端遍历, 每次把差值比较小的元素放入答案中然后将该指针向边界方向移动一下即可

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        
        int left = findLowerClosest(arr, x);
        int right = left+1;
        int[] result = new int[k];
        for(int i = 0; i< k;i++)
        {
            if(left < 0)
            {
                result[i] = arr[right++];
            }
            else if(right >= arr.length)
            {
                result[i] = arr[left--];
            }else
            {
                 if(x - arr[left] <= arr[right] - x)
                {
                    result[i] = arr[left];
                    left--;
                }
                else
                {
                    result[i] = arr[right];
                    right++;
                }  
            }   
        }
        
        Arrays.sort(result);
        List<Integer> list = new ArrayList<Integer>();
        for(int i = 0; i< k;i++)
        {
            list.add(result[i]);
        }
        return list;
    }
    
    public int findLowerClosest(int[] arr, int target)
    {
        int start = 0;
        int end = arr.length-1;
        while(start+1 < end)
        {
            int mid = start+ (end-start)/2;
            if(target == arr[mid])
            {
                return mid;
            }else if (target > arr[mid])
            {
                start = mid;
            }else
            {
                end = mid;
            }  
        }
        if(arr[end] <= target) return end;
        if(arr[start] <= target) return start;
        return -1;
    }
}