https://leetcode.com/problems/find-k-closest-elements
https://leetcode.com/articles/find-k-closest-elements/
Approach #2 Using Binary Search and Two Pointers
X. https://leetcode.com/problems/find-k-closest-elements/discuss/106419/O(log-n)-Java-1-line-O(log(n)-%2B-k)-Ruby
https://discuss.leetcode.com/topic/99178/java-o-logn-klogk-solution-with-priorityqueue-and-binary-search
1. 变种：找离某⼀一点最近的k个点
2. followup是⽤用pq的time complexity是nlogn，能否improve
https://github.com/mintycc/OnlineJudge-Solutions/blob/master/untag/Find%20Kth%20Closest%20Points/FindKthClosestPoints.java
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]
Example 2:
Input: [1,2,3,4,5], k=4, x=-1 Output: [1,2,3,4]
Note:
- The value k is positive and will always be smaller than the length of the sorted array.
- Length of the given array is positive and will not exceed 104
- Absolute value of elements in the array and x will not exceed 104
https://leetcode.com/articles/find-k-closest-elements/
Approach #2 Using Binary Search and Two Pointers
The original array has been sorted so we can take this advantage by the following steps. 1. If the target
xis less or equal than the first element in the sorted array, the first k elements are the result. 2. Similarly, if the target x is more or equal than the last element in the sorted array, the last k elements are the result. 3. Otherwise, we can use binary search to find the index of the element, which is equal (when this list has x) or a little bit larger than x (when this list does not have it). Then set low to its left k-1 position, and highto the right k-1 position of this index as a start. The desired k numbers must in this rang [index-k-1, index+k-1]. So we can shrink this range to get the result using the following rules. * If low reaches the lowest index 0 or the low element is closer to x than the high element, decrease the high index. * If high reaches to the highest index arr.size()-1 or it is nearer to x than the low element, increase the low index. * The looping ends when there are exactly k elements in [low, high], the subList of which is the result.- Time complexity : . is for the time of binary search, while is for shrinking the index range to k elements.
- Space complexity : . It is to generate the required sublist.
public List<Integer> findClosestElements(List<Integer> arr, int k, int x) {
int n = arr.size();
if (x <= arr.get(0)) {
return arr.subList(0, k);
} else if (arr.get(n - 1) <= x) {
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 - 1), high = Math.min(arr.size() - 1, index + k - 1);
while (high - low > k - 1) {
if (low < 0 || (x - arr.get(low)) <= (arr.get(high) - x))
high--;
else if (high > arr.size() - 1 || (x - arr.get(low)) > (arr.get(high) - x))
low++;
else
System.out.println("unhandled case: " + low + " " + high);
}
return arr.subList(low, high + 1);
}
}
https://discuss.leetcode.com/topic/99194/binary-search-and-two-pointers-18-ms
Noticing the array is sorted, so we can using binary search to get a rough area of target numbers, and then expand it to the left k-1 more and right k-1 more elements, then searching from the left to right. If the left element is more close or equal to the target number x than the right element, then move the right index to the left one step. Otherwise, move the left index to right one step. Once, the element between the left and right is k, then return the result.
public List<Integer> findClosestElements(List<Integer> arr, int k, int x) {
int n = arr.size();
if (x <= arr.get(0)) {
return arr.subList(0, k);
} else if (arr.get(n - 1) <= x) {
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 - 1), high = Math.min(arr.size() - 1, index + k - 1);
while (high - low > k - 1) {
if (low < 0 || (x - arr.get(low)) <= (arr.get(high) - x))
high--;
else if (high > arr.size() - 1 || (x - arr.get(low)) > (arr.get(high) - x))
low++;
else
System.out.println("unhandled case: " + low + " " + high);
}
return arr.subList(low, high + 1);
}
}
I binary-search for where the resulting elements start in the array. It's the first index
i so that arr[i] is better than arr[i+k] (with "better" meaning closer to or equally close to x). Then I just return the k elements starting there.
The binary search costs O(log n) (actually also just O(log (n-k)) and the
subList call probably only takes O(1). As @sagimann pointed out, subList returns a view, not a separate copy. So it should only take O(1). Can be seen for example in ArrayList's subList and the SubList constructor it calls. I also checked LinkedList, it gets its subList method inherited from AbstractList, where it also takes only O(1). And AbstractList is a basis for most lists.public List<Integer> findClosestElements(List<Integer> arr, int k, int x) {
int lo = 0, hi = arr.size() - k;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (x - arr.get(mid) > arr.get(mid+k) - x)
lo = mid + 1;
else
hi = mid;
}
return arr.subList(lo, lo + k);
}
Assume we are taking
We can binary research
We compare the distance between
A[i] ~ A[i + k -1].We can binary research
iWe compare the distance between
x - A[mid] and A[mid - k] - x
If
it means
and we have
So assign
x - A[mid] > A[mid + k] - x,it means
A[mid + 1] ~ A[mid + k] is better than A[mid] ~ A[mid + k - 1],and we have
mid smaller than the right i.So assign
left = mid + 1.https://discuss.leetcode.com/topic/99178/java-o-logn-klogk-solution-with-priorityqueue-and-binary-search
O(nlog(n)) Time Solution:
public List<Integer> findClosestElements(List<Integer> arr, int k, int x) {
Collections.sort(arr, (a,b) -> a == b ? a - b : Math.abs(a-x) - Math.abs(b-x));
arr = arr.subList(0, k);
Collections.sort(arr);
return arr;
}
O(n) Time Solution:
public List<Integer> findClosestElements(List<Integer> arr, int k, int x) {
List<Integer> less = new ArrayList<>(), greater = new ArrayList<>(),
lessResult = new LinkedList<>(), greaterResult = new LinkedList<>();
for (Integer i : arr) {
if (i <= x) less.add(i);
else greater.add(i);
}
Collections.reverse(less);
int i = 0, j = 0, n = less.size(), m = greater.size();
for (int size=0;size<k;size++) {
if (i < n && j < m) {
if (Math.abs(less.get(i) - x) <= Math.abs(greater.get(j) - x)) lessResult.add(less.get(i++));
else greaterResult.add(greater.get(j++));
}
else if (i < n) lessResult.add(less.get(i++));
else greaterResult.add(greater.get(j++));
}
Collections.reverse(lessResult);
lessResult.addAll(greaterResult);
return lessResult;
}1. 变种：找离某⼀一点最近的k个点
2. followup是⽤用pq的time complexity是nlogn，能否improve
https://github.com/mintycc/OnlineJudge-Solutions/blob/master/untag/Find%20Kth%20Closest%20Points/FindKthClosestPoints.java
public class Point {
int x, y, dist;
Point(int x, int y) {
this.x = x;
this.y = y;
dist = x * x + y * y;
}
}
public List<Point> findKthPQ(List<Point> points, int k) {
PriorityQueue<Point> pq = new PriorityQueue<>(new Comparator<Point>() {
public int compare(Point a, Point b) {
return b.dist - a.dist;
}
});
for (Point point : points) {
if (pq.size() < k) pq.add(point);
else if (point.dist < pq.peek().dist) {
pq.poll();
pq.add(point);
}
}
List<Point> ans = new ArrayList<>();
while (!pq.isEmpty()) ans.add(pq.poll());
return ans;
}
public List<Point> findKthQS(List<Point> points, int k) {
quickSelect(points, 0, points.size() - 1, k - 1);
List<Point> ans = new ArrayList<>();
for (int i = 0; i < k; i ++)
ans.add(points.get(i));
return ans;
}
private void quickSelect(List<Point> points, int l, int r, int k) {
if (l == r) return;
Point pivot = points.get(r);
int i = l, j = r - 1;
do {
while (i < r && points.get(i).dist < pivot.dist) i ++;
while (l < j && points.get(j).dist > pivot.dist) j --;
if (i < j) swap(points, i ++, j --);
} while (i < j);
swap(points, i, r);
if (i == k) return;
if (k < i) quickSelect(points, l, i - 1, k);
else quickSelect(points, i + 1, r, k);
}
private void swap(List<Point> points, int a, int b) {
Point tmp = points.get(a);
points.set(a, points.get(b));
points.set(b, tmp);
}
