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:
Input: [1,2,3,4,5], k=4, x=3
Output: [1,2,3,4]
Example 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
分析：
这题有两种解法，用于解决不同情况的问题：
1. 如果array 长度和 k 非常接近, 我们可以从array的最左边或者最右边移除 array.length - k个值就可以了。
2. 如果array长度远远大于k，我们可以先找到最大的一个数并且比x小的那个数，然后再以那个数开始从左右扩展，直到取到k个数。
方法一：
class Solution {
public List<Integer> findClosestElements(int[] arr, int k, int x) {
int left = , right = arr.length - ;
int remaining = arr.length - k;
while(remaining >= ) {
if (Math.abs(x - arr[left]) > Math.abs(arr[right] - x)) {
left++;
} else {
right--;
}
remaining--;
}
List<Integer> list = new ArrayList<>();
for (int i = left; i <= right; i++) {
list.add(arr[i]);
}
return list;
}
}
方法二：
class Solution {
public List<Integer> findClosestElements(int[] arr, int k, int x) {
int closest = closest(arr, x);
int left = closest;
int right = closest;
while (k > ) {
if (Math.abs(x - getValue(arr, left - )) <= Math.abs(x - getValue(arr, right + ))) {
left--;
} else {
right++;
}
k--;
}
List<Integer> list = new ArrayList<>();
for (int i = left; i <= right; i++) {
list.add(arr[i]);
}
return list;
}
private int closest(int[] arr, int x) {
int left = , right = arr.length - ;
while (left <= right) {
int mid = left + (right - left) / ;
if (arr[mid] == x) {
return mid;
} else if (arr[mid] < x) {
left = mid + ;
} else {
right = mid - ;
}
}
if (right < ) return left;
if (left >= arr.length) return right;
return Math.abs(x - arr[left]) > Math.abs(x - arr[right]) ? right : left;
}
private long getValue(int[] arr, int idx) {
if (idx < ) return Integer.MIN_VALUE;
if (idx >= arr.length) return Integer.MAX_VALUE;
return arr[idx];
}
}