题目 #

Given a sorted integer array arr, two integers k and x, return the k closest integers to x in the array. The result should also be sorted in ascending order.

An integer a is closer to x than an integer b if:

|a - x| < |b - x|, or
|a - x| == |b - x| and a < b

思路1 #

分析 #

双指针法，找到最接近x的数字，然后直接两边开始遍历

代码实现 #

 1func findClosestElements2(arr []int, k int, x int) []int {
 2	right := sort.SearchInts(arr, x)
 3	left := right - 1
 4	if left < 0 {
 5		return arr[:k]
 6	}
 7	for right-left < k+1 {
 8		if left < 0 {
 9			right++
10		} else if right >= len(arr) || arr[left]+arr[right] >= x+x {
11			left--
12		} else {
13			right++
14		}
15	}
16	return arr[left+1 : right]
17}

思路2 #

分析 #

写一个自定义cmp，直接排序取前k个

代码实现 #

 1func abs(x int) int {
 2	if x < 0 {
 3		return -x
 4	}
 5	return x
 6}
 7
 8func findClosestElements1(arr []int, k int, x int) []int {
 9	sort.SliceStable(arr, func(i, j int) bool { return abs(arr[i]-x) < abs(arr[j]-x) })
10	arr = arr[:k]
11	sort.Ints(arr)
12	return arr
13}