658. Find K Closest Elements
- Find K Closest Elements Medium
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:
The value k is positive and will always be smaller than the length of the sorted array.
Length of the given array is positive and will not exceed 104
Absolute value of elements in the array and x will not exceed 104
class Solution(object):
def findClosestElements(self, arr, k, x):
"""
:type arr: List[int]
:type k: int
:type x: int
:rtype: List[int]
"""
if arr==None:
return None
l, r = 0, len(arr) - 1
while l <= r:
mid = l + (r-l)//2
if arr[mid] < x:
l = mid + 1
else:
r = mid - 1
while r - l < k:
if l == 0: return arr[:k]
if r == len(arr): return arr[-k:]
if x - arr[l-1] <= arr[r] - x:
l -= 1
else:
r += 1
return arr[l:r]
start +(end – start)/ 2 与 (start + end)/ 2 的区别:
如果start或end的值或两者均为INT_MAX,将会导致整数溢出。
请多多指教。
文章标题:658. Find K Closest Elements
本文作者:顺强
发布时间:2020-04-12, 23:59:00
原始链接:http://shunqiang.ml/leetcode-685-find-k-closest-elements/版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。