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); } } }