给定一个排序好的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。

整数 a 比整数 b 更接近 x 需要满足：

  • |a - x| < |b - x| 或者

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

示例 1：

输入：arr = [1,2,3,4,5], k = 4, x = 3

输出：[1,2,3,4]

示例 2：

输入：arr = [1,2,3,4,5], k = 4, x = -1

输出：[1,2,3,4]

提示：

1 <= k <= arr.length

1 <= arr.length <= 104

arr 按升序排列

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

思路

找到数组中从左到右第一次出现x的下标（index），在该下标的左右维护两个指针，分别向左和向右递进来寻找其他更贴近的元素。

思路递推

以[1,2,3,4,5,5,5,6,8]为例，k为4，x为5，即寻找4个最接近5的数字，并由小到大排序返回。可以知道index为4，此时维护left指针为index-1即3，right指针为index即4，开始递进指针，过程如下：

  1. left = 3，right = 4，判断此时两指针元素与x的差值，发现right处的差值为0，即差值更小，则将right指针向右递进为5。
  2. left = 3，right = 5，判断此时两指针元素与x的差值，发现right处的差值为0，即差值更小，则将right指针向右递进为6。
  3. left = 3，right = 6，判断此时两指针元素与x的差值，发现right处的差值为0，即差值更小，则将right指针向右递进为7。
  4. left = 3，right = 7，判断此时两指针元素与x的差值，发现两处的差值均为1，即差值相等，根据提议，差值相等时更接近的值需要有更小的下标，则将left指针向左递进为2。
  5. 满足4个数字，退出搜寻。

此时还要注意几个边界值：

  • 左右指针不能够越出数组边界，当一侧到达边界时，即代表该侧无法再获取接近的值，只需要递进另一侧的指针，从另一侧获取更接近的值。
  • 怎么退出搜寻？不难发现可以通过k的递减来实现循环控制，由于right一开始值为index，即代表right指针一开始对应的元素肯定会被纳入结果，所以循环实际上只用进行k-1次。

代码实现：

public class LeetCode658 {

    public static List<Integer> findClosestElements(int[] arr, int k, int x) {
        //找到数组中最左端x对应的下标index
        //在index左右分别维护双指针left和right，其中left指针向左递进，right指针从index向右递进
        //在递进的过程中判断两边的差值，差值较小的一侧表明更接近x，对应侧的指针继续递进寻找下一个更接近的值
        //递进的过程中注意判断是否超出数组边界，若当前侧超出数组边界则另一侧指针递进，直到right-left = k为止
        int index = leftBondBinarySearch(arr, x);
        int left = index - 1,right = index;
        List<Integer> result = new ArrayList<>();
        //循环只能进行k-1次，因为一开始right下标对应的元素就是本身，即差值为0，肯定会被纳入结果，因此只要再找出k-1个数即可
        while (k-- > 0){
            if (left < 0)
                //超出左边界，右侧指针递进
                right++;
            else if (right > arr.length - 1)
                //超出右边界，左侧指针递进
                left--;
            else if (x - arr[left] <= arr[right] - x)
                //两侧差值取小的一侧递进，如果相等则取下标更小的元素
                left--;
            else
                right++;
        }
        //此时left和right的差值为k+1，从left+1处开始获取第一个元素
        for (int i = left+1; i < right; i++) {
            result.add(arr[i]);
        }
        return result;
    }

    /**
     * @Author huang.zh
     * @Description 找到数组中最左端出现的值为target的元素下标，即二分左边界搜索
     * @Date 9:43 PM 2023/9/5
     * @Param [arr, target]
     * @return
     **/
    private static int leftBondBinarySearch(int[] arr,int target){
        int left = 0,right = arr.length - 1;
        while (left < right){
            int mid = left + (right - left)/2;
            if (arr[mid] == target){
                //命中元素，右指针重置，在[left,mid]中寻找更左端的值为target的元素
                right = mid;
            } else if (arr[mid] < target){
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }


    public static void test(){
        List<Integer> list = findClosestElements(new int[]{1, 2, 3, 4, 5}, 2, 4);
        System.out.println(Arrays.toString(list.toArray()));
    }
}