【LeetCode通关全记录】658. 找到 K 个最接近的元素
题目地址👉658. 找到 K 个最接近的元素
解法1：删除法（双指针）
从数组的两端不断删除与x的差值更大的元素直到数组长度为k，看到这题第一个想到的就是这个方法，也是一个比较简单的方法，可惜的是在n很大k很小的时候效率不高。
注意：因为若x在数组中那么x比arr[0]大而比arr[len(arr)-1]小，所以如果不想调用math.Abs()或者自己写绝对值函数取绝对值的话判断条件就需要写成x-arr[0] > arr[len(arr)-1]-x。x不在数组中的情况也是类似的考虑方法。
func findClosestElements(arr []int, k int, x int) []int {
for len(arr) > k {
if x-arr[0] > arr[len(arr)-1]-x {
arr = arr[1:]
} else {
arr = arr[:len(arr)-1]
}
}
return arr
}
执行用时: 32 ms（超过97%的Golang提交记录）
内存消耗: 6.9 MB（超过39%的Golang提交记录）
时间复杂度：O(n - k)
空间复杂度：O(1)
解法2：二分查找
标准的二分查找代码，只不过判断条件改成了判断x-arr[mid]和arr[mid+k]-x的大小关系而不是判断x与arr[mid]是否相等，并且因为要返回k个元素所以起始条件中的右边界s为len(arr)-k而不是len(arr)。
这种方法不如删除法好想到，但是最坏时间复杂度更优秀一些。
func findClosestElements(arr []int, k int, x int) []int {
s, g := len(arr)-k, 0
for g < s {
mid := (s + g) / 2
if x-arr[mid] > arr[mid+k]-x {
g = mid + 1
} else {
s = mid
}
}
return arr[g : g+k]
}
执行用时: 36 ms（超过85%的Golang提交记录）
内存消耗: 6.9 MB（超过62%的Golang提交记录）
时间复杂度：O(logn + k)
空间复杂度：O(1)
