658. Find K Closest Elements #

题目 #

Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.

Example 1:

Input: [1,2,3,4,5], k=4, x=3
Output: [1,2,3,4]

Example 2:

Input: [1,2,3,4,5], k=4, x=-1
Output: [1,2,3,4]

Note:

1. The value k is positive and will always be smaller than the length of the sorted array.
2. Length of the given array is positive and will not exceed 10^4
3. Absolute value of elements in the array and x will not exceed 10^4

UPDATE (2017/9/19): The arr parameter had been changed to an array of integers (instead of a list of integers). Please reload the code definition to get the latest changes.

题目大意 #

给定一个排序好的数组，两个整数 k 和 x，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。如果有两个数与 x 的差值一样，优先选择数值较小的那个数。

说明:

1. k 的值为正数，且总是小于给定排序数组的长度。
2. 数组不为空，且长度不超过 104
3. 数组里的每个元素与 x 的绝对值不超过 104  

更新(2017/9/19): 这个参数 arr 已经被改变为一个整数数组（而不是整数列表）。 请重新加载代码定义以获取最新更改。

解题思路 #

• 给出一个数组，要求在数组中找到一个长度为 k 的区间，这个区间内每个元素距离 x 的距离都是整个数组里面最小的。
• 这一题可以用双指针解题，最优解法是二分搜索。由于区间长度固定是 K 个，所以左区间最大只能到 len(arr) - K (因为长度为 K 以后，正好右区间就到数组最右边了)，在 [0,len(arr) - K] 这个区间中进行二分搜索。如果发现 a[mid] 与 x 距离比 a[mid + k] 与 x 的距离要大，说明要找的区间一定在右侧，继续二分，直到最终 low = high 的时候退出。逼出的 low 值就是最终答案区间的左边界。

代码 #

package leetcode

import "sort"

// 解法一 库函数二分搜索
func findClosestElements(arr []int, k int, x int) []int {
	return arr[sort.Search(len(arr)-k, func(i int) bool { return x-arr[i] <= arr[i+k]-x }):][:k]
}

// 解法二 手撸二分搜索
func findClosestElements1(arr []int, k int, x int) []int {
	low, high := 0, len(arr)-k
	for low < high {
		mid := low + (high-low)>>1
		if x-arr[mid] > arr[mid+k]-x {
			low = mid + 1
		} else {
			high = mid
		}
	}
	return arr[low : low+k]
}