本文共 1905 字，大约阅读时间需要 6 分钟。
Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.
Example 1:
Input: [1,2,3,4,5], k=4, x=3
Output: [1,2,3,4]
jiuzhang solution: 二分法 + 双指针
先通过二分法找到大于target的最小数。再用背向双指针以前面找到的那个数为起点找到k个最接近target的数。 这里需要注意的是，大于target的最小数不一定是最接近的k个数之一，因此不能直接把这个数加入到result当中，也需要经过判断class Solution { public List findClosestElements(int[] arr, int k, int x) { List result = new ArrayList<>(); if(arr == null || arr.length == 0) return result; if(arr.length < k) return result; //backward two pointer int idx = firstElemt(arr, x); int start = idx - 1, end = idx; for(int i = 0; i < k; i++) { if(start < 0) { result.add(arr[end++]); } else if(end > arr.length - 1) { result.add(arr[start--]); } else { if(x - arr[start] <= arr[end] - x) { result.add(arr[start--]); } else { result.add(arr[end++]); } } } //sort方法不会将排序后数组返回，因此不能直接将这个语句return Collections.sort(result); return result; } //find the smallest element greater than target private int firstElemt(int[] A, int target) { int start = 0, end = A.length - 1; while(start + 1 < end) { int mid = start + (end - start) / 2; if(A[mid] >= target) { end = mid; } else { start = mid; } } if(A[start] >= target) { return start; } if(A[end] >= target) { return end; } //all of elements are smaller than target return A.length; }} 转载地址：http://hkqvb.baihongyu.com/