【2022-08-25每日一题】658. 找到 K 个最接近的元素
2022-08-25
2分钟阅读时长
2022-08-25每日一题：658. 找到 K 个最接近的元素
- 难度：Medium
- 标签：数组 、 双指针 、 二分查找 、 排序 、 堆（优先队列）
给定一个 排序好 的数组 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.length1 <= arr.length <= 104arr按 升序 排列-104 <= arr[i], x <= 104
方法一：排序
思路
首先将数组 arr 按照「更接近」的定义进行排序，如果 a 比 b 更接近 x，那么 a 将排在 b 前面。排序完成之后，k 个最接近的元素就是数组arr 的前 k 个元素，将这 k 个元素从小到大进行排序后，直接返回。
代码
func findClosestElements(arr []int, k int, x int) []int {
sort.SliceStable(arr, func(i, j int) bool {
return abs(arr[i]-x) < abs(arr[j]-x)
})
ans := arr[:k]
sort.Ints(ans)
return ans
}
func abs(a int) int {
if a < 0 {
return -a
}
return a
}
复杂度分析
时间复杂度：O(nlogn)，其中 n 是数组 arr 的长度。排序需要 OO(nlogn)。
空间复杂度：O(logn)。返回值不计算时间复杂度。排序需要 O(logn) 的栈空间。
方法二：排除法（双指针）
参考题解
思路
- 如果左边界与
x的差值的绝对值较小，删除右边界； - 如果右边界与
x的差值的绝对值较小，删除左边界； - 如果左、右边界与
x的差值的绝对值相等，删除右边界。
func findClosestElements(arr []int, k int, x int) []int {
size, left := len(arr), 0
for removeNums, right := size-k, size-1; removeNums > 0; removeNums-- {
if x - arr[left] <= arr[right] - x {
right--
} else {
left++
}
}
return arr[left:left+k]
}
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(1)。
方法三：二分+双指针
参考题解
func findClosestElements(arr []int, k int, x int) []int {
left, right := 0, len(arr) - k
for left < right; {
mid := left + (right - left) >> 1
// 尝试从长度为 k + 1 的连续子区间删除一个元素
// 从而定位左区间端点的边界值
if x - arr[mid] > arr[mid+k] - x {
// 下一轮搜索区间是 [mid + 1..right]
left = mid + 1
} else {
// 下一轮搜索区间是 [left..mid]
right = mid
}
}
return arr[left:left+k]
}
参考题解
思路
假设数组长度为 nn，注意到数组 arr 已经按照升序排序，我们可以将数组 arr 分成两部分，前一部分所有元素 [0,left] 都小于 x，后一部分所有元素 [right,n−1] 都大于等于 x，left 与 right 都可以通过二分查找获得。
left 和 right 指向的元素都是各自部分最接近 x 的元素，因此我们可以通过比较 left 和right 指向的元素获取整体最接近 x 的元素。如果 x−arr[left]≤arr[right]−x，那么将 left 减一，否则将 right 加一。相应地，如果 left 或 right 已经越界，那么不考虑对应部分的元素。
最后，区间 [left+1,right−1] 的元素就是我们所要获得的结果，返回答案既可。
func findClosestElements(arr []int, k int, x int) []int {
right := sort.SearchInts(arr, x)
left := right - 1
for ; k > 0; k-- {
if left < 0 {
right++
} else if right >= len(arr) || x - arr[left] <= arr[right] - x {
left--
} else {
right++
}
}
return arr[left+1:right]
}
复杂度分析
时间复杂度：O(logn+k)。其中 n 是数组 arr 的长度。二分查找需要 O(logn)，双指针查找需要 O(k)。
空间复杂度：O(1)。