原题
给定一个排序好的数组,两个整数 k
和 x
,从数组中找到最靠近 x
(两数之差最小)的 k
个数。返回的结果必须要是按升序排好的。如果有两个数与 x
的差值一样,优先选择数值较小的那个数。
示例1:
输入: [1,2,3,4,5], k=4, x=3
输出: [1,2,3,4]
示例2:
输入: [1,2,3,4,5], k=4, x=-1
输出: [1,2,3,4]
说明:
- k 的值为正数,且总是小于给定排序数组的长度。
- 数组不为空,且长度不超过 104
- 数组里的每个元素与 x 的绝对值不超过 104
解法
思想
- 按照差值排序
- 双指针
代码
- 排序
public List<Integer> findClosestElements(List<Integer> arr, int k, int x) {
Collections.sort(arr, (a,b) -> a == b ? a - b : Math.abs(a-x) - Math.abs(b-x));
arr = arr.subList(0, k);
Collections.sort(arr);
return arr;
}
- 双指针(作者:liweiwei1419)
public class Solution {
public List<Integer> findClosestElements(int[] arr, int k, int x) {
int size = arr.length;
int left = 0;
int right = size - 1;
int removeNums = size - k;
while (removeNums > 0) {
if (x - arr[left] <= arr[right] - x) {
right--;
} else {
left++;
}
removeNums--;
}
List<Integer> res = new ArrayList<>();
for (int i = left; i < left + k; i++) {
res.add(arr[i]);
}
return res;
}
}
原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode658-%e6%89%be%e5%88%b0k%e4%b8%aa%e6%9c%80%e6%8e%a5%e8%bf%91%e7%9a%84%e5%85%83%e7%b4%a0/