【LeetCode通關全記錄】658. 找到 K 個最接近的元素
題目地址??658. 找到 K 個最接近的元素
解法1：刪除法（雙指針）
從數(shù)組的兩端不斷刪除與x的差值更大的元素直到數(shù)組長度為k雀监，看到這題第一個想到的就是這個方法，也是一個比較簡單的方法，可惜的是在n很大k很小的時候效率不高疤剑。
注意：因為若x在數(shù)組中那么x比arr[0]大而比arr[len(arr)-1]小匠璧，所以如果不想調(diào)用math.Abs()或者自己寫絕對值函數(shù)取絕對值的話判斷條件就需要寫成x-arr[0] > arr[len(arr)-1]-x贩挣。x不在數(shù)組中的情況也是類似的考慮方法。
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
}
執(zhí)行用時: 32 ms（超過97%的Golang提交記錄）
內(nèi)存消耗: 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)秋忙。
這種方法不如刪除法好想到彩掐，但是最壞時間復雜度更優(yōu)秀一些。
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]
}
執(zhí)行用時: 36 ms（超過85%的Golang提交記錄）
內(nèi)存消耗: 6.9 MB（超過62%的Golang提交記錄）
時間復雜度：O(logn + k)
空間復雜度：O(1)
