leetcode658_找到k个最接近的元素

给定一个排序好的数组，两个整数 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 的值为正数，且总是小于给定排序数组的长度。
数组不为空，且长度不超过 10^4
数组里的每个元素与 x 的绝对值不超过 10^4

思路：

由于数组有序，所以最后找到的k个元素也一定是有序的，其实就是返回了一个长度为k的子数组，相当于在长度为n的数组中去掉n-k个数字， 而且去掉的顺序肯定是从两头开始去，因为距离x最远的数字肯定在首尾出现。每次比较首尾两个数字跟x的距离，将距离大的那个数字删除，直到剩余的数组长度为k为止。

//留下最近的  也就是去掉最远的  直到数组长度为k
	 public List<Integer> findClosestElements1(int[] arr, int k, int x) {
			 List<Integer> res=new ArrayList<>();
			 int len=arr.length;
			 int left=0;
			 int right=len-1;
			 while (len>k) {
				if (Math.abs(arr[left]-x)>Math.abs(arr[right]-x)) {
					left++;
				}else {
					right--;
				}
				len--;
			}
	        for (int index = left; index <=right; index++) {
	                  res.add(arr[index]);       
			}
		     return res;	        
	    }

还可以利用二分的方法  找到距离最近区间的起点

 public List<Integer> findClosestElements(int[] arr, int k, int x) {
	        List<Integer> res = new ArrayList<>();
	        int start = 0, end = arr.length-k;
	        while(start<end){
	            int mid = start + (end-start)/2;
	            if(Math.abs(arr[mid]-x)>Math.abs(arr[mid+k]-x)){ //中位数距离x比较远  所以看右半部分 
	                start = mid+1;
	            } else {
	                end = mid;
	            }
	        }
	        for(int i=start; i<start+k; i++){
	            res.add(arr[i]);
	        }
	        return res;
	    }