Find K Closest Elements


Note that space complexity of a.subList may be O(1) because subList is done inplace when supported by the implementation, returning a "view" over the original list, as explained in the List interface spec. For example, if you look at the ArrayList implementation and its SubList private class.

class Solution { public: vector<int> findClosestElements(vector<int>& arr, int k, int x) { auto h = arr.size()  k; auto l = 0; while (l < h) { auto mid = (l + h) / 2; if (abs(arr[mid]  x) <= abs(arr[k + mid]  x)) { h = mid; } else { l = mid + 1; } } vector<int> rst(arr.begin() + h, arr.begin() + h + k); return rst; } };
I think my solution is O(log(n)) in search phase

@Albert_G The problem says "array" five times. And the variable is called
arr
. I think it's fair to assume that it's an array.

Collections.sort()
There is some compile error with the first sort solution. Anyway, the idea is neat. The following is an implementation using Java 8 stream.
class Solution { public List<Integer> findClosestElements(int[] arr, int k, int x) { final List<Integer> ans = Arrays.stream(arr).boxed().sorted(Comparator.comparingInt(a > Math.abs(a  x))).collect(Collectors.toList()); Collections.sort(ans.subList(0, k)); return ans.subList(0, k); } }
BTW,
Collections.sort()
actually uses extra space. It does the following in the background. You may check its source code here.Object[] a = list.toArray(); Arrays.sort(a);
And there is a typo in the explanation:
Collections.sort()
uses merge sortBinary search
I think the most difficult point is to understand
index = index  1
. Well,Collections.binarySearch()
returns(insertion point)  1
, which isindex
. Soindex  1
is justinsertion point
, which is the index of the element if it is to be added to the array and also keep the array sorted.For example, for
arr = [2, 3, 5, 6]
, ifx = 1
, the insertion point will be at0
(insertingx
at index0
will still keeparr
sorted); similarly, ifx = 7
, the insertion point will become4
; and ifx = 4
, the insertion point will become2
.BTW, the code can be simplified a little bit.
class Solution { public List<Integer> findClosestElements(int[] a, int k, int x) { final List<Integer> arr = Arrays.stream(a).boxed().collect(Collectors.toList()); final int n = arr.size(); if (x <= arr.get(0)) { return arr.subList(0, k); } else if (x >= arr.get(n  1)) { return arr.subList(n  k, n); } else { int index = Collections.binarySearch(arr, x); if (index < 0) { index = index  1; } int low = Math.max(0, index  k); int high = Math.min(n  1, index + k  1); while (high  low + 1 > k) { if (x  arr.get(low) <= arr.get(high)  x) { high; } else { low++; } } return arr.subList(low, high + 1); } } }

the second solution. In the while loop：while (high  low > k  1)，I don't think you have to check if low <0 or high > arr.size()  1，since what you do with int low = Math.max(0, index  k  1), high = Math.min(arr.size()  1, index + k  1), has guaranteed that low and high are valid.

Hey, I've faced a test, and understood that I had misunderstood the task.
Maybe I'm even a single person who did this mistake, but for me preferences sound like: Select the closest by distance
 If distances are the same  select smaller element
So I was surprised when I got this result, because 9 is much closer to 4 than 0.
I think it would be great to clarify this in description.
Input:
[0,1,1,1,2,3,6,7,8,9]
9
4
Output:
[1,1,1,2,3,6,7,8,9]
Expected:
[0,1,1,1,2,3,6,7,8]

class Solution {
public List<Integer> findClosestElements(int[] arr, int k, int x) {
List<Integer> list = new ArrayList<>();
if(arr.length == 0  arr == null) {
return list;
}
if (x <= arr[0]) {
for(int i = 0; i < k; i++) {
list.add(arr[i]);} return list; } if (x >= arr[arr.length  1]) { for(int i = arr.length  k ; i <= arr.length  1; i++) { list.add(arr[i]); } //Arrays.sort(list); return list; } int index = binarySearch(arr, x); int low = Math. max(0, index  k + 1); int high = Math.min(arr.length  1, index + k  1); // if arr[index]  arr[low] <= arr[high]  arr[index], high while(high  low > k  1){ if (low < 0  x  arr[low] <= arr[high]  x){ high; } else if (high > arr.length1  x  arr[low] > arr[high]  x){ low++; } } for(int i = low; i <= high; i++) { list.add(arr[i]); } return list; } private int binarySearch(int[] arr, int x) { int start = 0, end = arr.length  1; while(start + 1 < end) { int mid = start + (end  start) / 2; if(arr[mid] == x) { return mid; } if(arr[mid] > x) { end = mid; } else { start = mid; } } if(arr[start] == x){return start;} if(arr[end] == x){return end;} return start; }
}