class Solution {
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
}
};
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.length1 <= arr.length <= 104arr 按 升序 排列-104 <= arr[i], x <= 104原站题解
golang 解法, 执行用时: 36 ms, 内存消耗: 6.8 MB, 提交时间: 2022-08-25 10:23:43
func findClosestElements(arr []int, k, 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]
}
golang 解法, 执行用时: 44 ms, 内存消耗: 6.8 MB, 提交时间: 2022-08-25 10:23:17
func findClosestElements(arr []int, k, x int) []int {
// 稳定排序，在绝对值相同的情况下，保证更小的数排在前面
sort.SliceStable(arr, func(i, j int) bool { return abs(arr[i]-x) < abs(arr[j]-x) })
arr = arr[:k]
sort.Ints(arr)
return arr
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
python3 解法, 执行用时: 60 ms, 内存消耗: 16.2 MB, 提交时间: 2022-08-25 10:22:46
class Solution:
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
arr.sort(key=lambda v: abs(v-x))
return sorted(arr[:k])
python3 解法, 执行用时: 68 ms, 内存消耗: 16.2 MB, 提交时间: 2022-08-25 10:22:12
class Solution:
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
right = bisect_left(arr, x)
left = right - 1
for _ in range(k):
if left < 0:
right += 1
elif right >= len(arr) or x - arr[left] <= arr[right] - x:
left -= 1
else:
right += 1
return arr[left + 1: right]