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.length1 <= arr.length <= 104arris 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
}