658 Find K Closest Elements

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:

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

Example 2:

1
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

题目大意

给定一个有序数组,在数组中找到与 x 接近的 k 个元素。

解题思路

使用二分查找找到最接近 x 的数组下标 index
从子序列 index-k...index+k 中找到最接近 xk 个元素。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
func findClosestElements(_ arr: [Int], _ k: Int, _ x: Int) -> [Int] {
func binarySearch() -> Int {
var l = 0
var r = arr.count - 1
while l + 1 < r {
let mid = (l + r) / 2
if arr[mid] == x {
return mid
}else if arr[mid] > x {
r = mid
}else {
l = mid
}
}
return r
}
guard arr.count > 0 else { return [] }
if arr[0] > x { return Array(arr[0..<min(k, arr.count)]) }
if arr.last! < x { return Array(arr[max(arr.count - k, 0)..<arr.count]) }
let index = binarySearch()
var l = max(0, index - k)
var r = min(index + k, arr.count - 1)
while r - l != k - 1 {
if x - arr[l] > arr[r] - x {
l += 1
}else {
r -= 1
}
}
return Array(arr[l...r])
}
}
0%