给定一个排序好的数组 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()));
    }
}
Java