D.二分查找-进阶——658. 找到 K 个最接近的元素

题目链接：658. 找到 K 个最接近的元素（中等）

算法原理：

解法一：排序

19ms击败13.08%

时间复杂度O(NlogN)

这个解法其实挺暴力的，直接用把arr全扔链表里，然后按照题目要求把链表排序，最后取出前K个即可，别忘了返回前排个序

解法二：双指针+二分查找

3ms击败100.00%

时间复杂度O(NlogN)

利用题目给的arr已升序排序的条件，可根据x把arr分成两部分，前一部分都<x，后一部分都≥x，我们可以只用一次二分查找即可，先确定right，那么left就是right-1，确定right用到求最左端点模型👇

优选算法-二分：18.在排序数组中查找元素的第一个和最后一个位置

然后通过移动left和right确定一个[left+1,right-1]区间，这个区间内的元素即答案

如何移动呢？👇

如果left越界：left<0，只能right++

如果right越界:right>=arr.length，只能left--

都不越界就按题意来移动：

如果x和left的差<=x和right的差，就left--，因为差值相同时，题目规定取小的

如果x和left的差>x和right的差，就right++

Java代码：

class Solution { //解法一：排序 public List<Integer> findClosestElements(int[] arr, int k, int x) { List<Integer> list=new ArrayList<>(); for(int a:arr) list.add(a); Collections.sort(list,new Comparator<Integer>(){ @Override public int compare(Integer a,Integer b){ if(Math.abs(x-a)!=Math.abs(x-b)) return Math.abs(x-a)-Math.abs(x-b); else return a-b; } }); List<Integer> ret=list.subList(0,k); Collections.sort(ret); return ret; } }

class Solution { //解法二：双指针+二分查找 public List<Integer> findClosestElements(int[] arr, int k, int x) { int right=binarySearch(arr,x); int left=right-1; //维护[left,right]作为结果区间 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> ret=new ArrayList<>(); for(int i=left+1;i<right;i++) ret.add(arr[i]); return ret; } public int binarySearch(int[] arr,int x){ //最左端点模型 int left=0,right=arr.length-1; while(left<right){ int mid=left+(right-left)/2; if(arr[mid]<x) left=mid+1; else right=mid; } return left; } }