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
}