658. Find K Closest Elements 找到 K 个最接近的元素

# 题目描述：

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 104
3. Absolute value of elements in the array and x will not exceed 104

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.

# 解题方法

# 方法一：堆

``````class Solution(object):
def findClosestElements(self, arr, k, x):
"""
:type arr: List[int]
:type k: int
:type x: int
:rtype: List[int]
"""
N = len(arr)
sub = [((arr[i] - x) ** 2, i) for i in range(N)]
heapq.heapify(sub)
return sorted([arr[heapq.heappop(sub)[1]] for i in range(k)])
``````

# 方法二：双指针

``````class Solution(object):
def findClosestElements(self, arr, k, x):
"""
:type arr: List[int]
:type k: int
:type x: int
:rtype: List[int]
"""
while len(arr) > k:
if x - arr[0] <= arr[-1] - x:
arr.pop()
else:
arr.pop(0)
return arr
``````

# 方法三：二分查找

``````class Solution(object):
def findClosestElements(self, arr, k, x):
"""
:type arr: List[int]
:type k: int
:type x: int
:rtype: List[int]
"""
left = 0
right = len(arr) - k
while left < right:
mid = left + (right - left) / 2
if x - arr[mid] > arr[mid + k] - x:
left = mid + 1
else:
right = mid
return arr[left : left + k]
``````

http://www.cnblogs.com/grandyang/p/7519466.html

# 日期

2018 年 10 月 8 日 —— 终于开学了。