【LeetCode刷题-二分查找】--658.找到K个最接近的元素

658.找到K个最接近的元素

方法一：二分查找+双指针

• 假设数组长度为n，数组arr已经按照升序排序，可以将数组arr分为两部分，前一部分所有元素[0,left]都小于x，后一部分[right,n-1]都大于等于x，left与right都可以通过二分查找获得
• left和right指向的元素都是各自部分最接近x的元素，因此我们可以通过比较left和right指向的元素获取整体最接近x的元素，如果x-arr[left]≤arr[right]-x，则将left-1，否则将right+1，相应地，如果left或right已经越界，那么不考虑对应部分的元素
• 最后，区间[left+1,right-1]的元素就是需要获得的结果

class Solution {public List<Integer> findClosestElements(int[] arr, int k, int x) {int right = binarrySearch(arr,x);int left = right - 1;while(k-->0){if(left < 0){right++;}else if(right >= arr.length){left--;}else if(x - arr[left] <= arr[right] -x){left--;}else{right++;}}List<Integer> ans = new ArrayList<>();for(int i = left+1;i<right;i++){ans.add(arr[i]);}return ans;}public int binarrySearch(int[] arr,int x){int low = 0,high = arr.length - 1;while(low < high){int mid = low + (high - low) / 2;if(arr[mid] >= x){high = mid;}else{low = mid + 1;}}return low;}
}

方法二：二分查找

class Solution {public List<Integer> findClosestElements(int[] arr, int k, int x) {int left = 0,right = arr.length -1;while(right - left + 1>k){if(Math.abs(arr[left] - x) > Math.abs(arr[right] - x)){left++;}else{right--;}}List<Integer> result = new ArrayList<>();for (int i = left; i <= right; i++) {result.add(arr[i]);  // 将选定范围内的元素添加到结果列表}return result;}
}