LeetCode 658. Find K Closest Elements 2019-08-20

题目描述

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

k 的值为正数,且总是小于给定排序数组的长度。数组不为空,且长度不超过 10^4数组里的每个元素与 x 的绝对值不超过 10^4

tag

二分 双指针

样例

1
2
3

输入: [1,2,3,4,5], k=4, x=-1
输出: [1,2,3,4]

算法1

(二分) O(logn)
思路


https://leetcode-cn.com/problems/find-k-closest-elements/solution/pai-chu-fa-shuang-zhi-zhen-er-fen-fa-python-dai-ma/


https://leetcode-cn.com/problems/find-k-closest-elements/solution/658-zhao-dao-k-ge-zui-jie-jin-de-yuan-su-cer-fen-s/

复杂度分析:
python 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
l = len(arr)
left = 0
right = l - k

while left < right:

mid = (left + right) // 2

if x - arr[mid] > arr[mid + k] - x:
left = mid + 1
else:
right = mid


return arr[left : left + k]

算法2

(双指针) O(n)
思路
复杂度分析:
python 代码