算法随笔_15: 找到K个最接近的元素
上一篇:算法随笔_14: 平方数之和-CSDN博客
题目描述如下:
给定一个 排序好 的数组 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]
算法思路:
由于给定的数组已经是排好序的。我们可以用二分查找法，先找到最靠近x的两个元素:
1. 小于或等于x的所有数中的最大值，即，x左侧的最大值。我们设它的下标为left_ind。
2. 大于x的所有数中的最小值，即，x右侧的最小值，我们设它的下标为right_ind。
找到这两个下标后，我们循环执行下面的步骤k次，来找到k个最接近的元素:
==================
我们判断x与arr[left_ind]的距离是否小于x与arr[right_ind]的距离。有两种情况:
a. 如果小于，说明arr[left_ind]是第一接近x的元素。为了找到第二接近x的元素，我们需要向左移动left_ind下标，即，left_ind=left_ind-1。
b. 如果大于，说明arr[right_ind]是第一接近x的元素。我们需要向右移动right_ind下标，即，right_ind=right_ind+1。
重复此步骤。
===================
此算法的时间复杂度为O(logn+k) 。