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|
anda < 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
}