658. Find K Closest Elements

Medium

Given a sorted integer array arr, two integers k and x, return the k closest integers to x in the array. The result should also be sorted in ascending order.

An integer a is closer to x than an integer b if:

• |a - x| < |b - x|, or

• |a - x| == |b - x| and a < b

Example 1:

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

Example 2:

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

Constraints:

• 1 <= k <= arr.length

• 1 <= arr.length <= 104

• arr is sorted in ascending order.

• -104 <= arr[i], x <= 104

解題

給的 arr 是一個排序好的陣列，而數字 k 的值可能會有：小於陣列所有數字、大於陣列所有數字、在陣列最小數與最大數之間 這三種可能。第一種可能的話，最遠的值會集中在陣列末端；第二種可能的話，最遠的值最集中在陣列首；第三種可能則首尾都可能。所以我們可以從首尾開始檢查，每次都移除一個最遠的，直到留下 k 個最近的數字。

Runtime: 44 ms, faster than 89.61%

Memory Usage: 6.8 MB, less than 93.85%

func findClosestElements(arr []int, k int, x int) []int {
    // 從頭尾開始移除
    for len(arr) != k {
        if abs(arr[len(arr)-1] - x) >= abs(arr[0] - x) {
            arr = arr[:len(arr)-1]
        } else {
            arr = arr[1:]
        }
    }
    
    return arr
}

func abs(num int) int {
    if num < 0 { return -num }
    return num
}