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 中找到最接近 x 的 k 个元素。

代码

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%