找到 K 个最接近的元素
# 📃 题目描述
题目链接:658. 找到 K 个最接近的元素 (opens new window)
# 🔔 解题思路
美团一面的原题,一开始想的暴力排序,后来面试官引导了很久才想出来二分查找 + 双指针
二分查找到 x 的位置(注意这里 x 可能不存在于 arr 中),然后左右指针找 k 个最接近 x 的数
class Solution {
public List<Integer> findClosestElements(int[] arr, int k, int x) {
List<Integer> list = new ArrayList<>();
int index = getX(arr, x);
// 这里【不】应该初始化为 left = index, right = index + 1
// ex: [0,0,1,2,3,3,4,7,7,8] k = 3, x = 5
int left = index - 1, index;
while (k != 0 && (left >= 0 || right < arr.length)) {
int l = (left >= 0) ? Math.abs(arr[left] - x) : Integer.MAX_VALUE;
int r = (right < arr.length) ? Math.abs(arr[right] - x) : Integer.MAX_VALUE;
if (l <= r) {
left --;
}
else {
right ++;
}
k --;
}
for (int i = left + 1; i <= right - 1; i ++) {
list.add(arr[i]);
}
return list;
}
// 找到 x 的下标,如果 x 不存在,返回第一个比 x 大的元素的下标
private int getX(int[] arr, int x) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (arr[mid] == x) {
return mid;
}
else if (arr[mid] > x) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
return left;
}
}
# 💥 复杂度分析
- 空间复杂度:
- 时间复杂度:
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10