3分钟
LeetCode算法手记:658.找到 K 个最接近的元素
给定一个排序好的数组 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,开始递进指针,过程如下:
- left = 3,right = 4,判断此时两指针元素与x的差值,发现right处的差值为0,即差值更小,则将right指针向右递进为5。
- left = 3,right = 5,判断此时两指针元素与x的差值,发现right处的差值为0,即差值更小,则将right指针向右递进为6。
- left = 3,right = 6,判断此时两指针元素与x的差值,发现right处的差值为0,即差值更小,则将right指针向右递进为7。
- left = 3,right = 7,判断此时两指针元素与x的差值,发现两处的差值均为1,即差值相等,根据提议,差值相等时更接近的值需要有更小的下标,则将left指针向左递进为2。
- 满足4个数字,退出搜寻。
此时还要注意几个边界值:
- 左右指针不能够越出数组边界,当一侧到达边界时,即代表该侧无法再获取接近的值,只需要递进另一侧的指针,从另一侧获取更接近的值。
- 怎么退出搜寻?不难发现可以通过k的递减来实现循环控制,由于right一开始值为index,即代表right指针一开始对应的元素肯定会被纳入结果,所以循环实际上只用进行k-1次。