一刷 05/2022
Version #2 Binary Search To Find The Left Bound[TODO]
Time O(log(n - k) + k)
Space O(1)
Not working version
有一个反例就是当 mid= 3, mid + k = 6的时候他们同时指向element 2
但是此时需要我们选择larger index
就没懂
index [0,1,2,3,4,5,6,7,8]
arr [1,1,2,2,2,2,2,3,3]
[1,1,2,2,2,2,2,3,3]
3
3
class Solution {
public List<Integer> findClosestElements(int[] arr, int k, int x) {
if (arr == null) {
return new ArrayList<>();
}
// Binary search to find the left bound
int start = 0, end = arr.length - k;
System.out.printf("start: %d, end: %d", start, end);
while (start + 1 < end) {
int mid = start + (end - start) / 2;
// arr[mid] and arr[mid + k] there can only 1 be in the final answer
if (Math.abs(arr[mid] - x) > Math.abs(arr[mid + k] - x)) {
start = mid + 1;
} else {
end = mid;
}
}
System.out.printf("start: %d, end: %d", start, end);
// ... start end ... start + k, end + k
if (start + k < arr.length && Math.abs(arr[start] - x) > Math.abs(arr[start + k] - x)) {
start = end;
}
List<Integer> res = new ArrayList<>();
while (k-- > 0) {
res.add(arr[start]);
start++;
}
return res;
}
}
Version #1 Binary Search + Sliding window
一遍bug free就过了，我真棒
重点是在算insertion index的时候考虑到各种Corner case
Time O(logN + k)
Space O(1)
Memory Usage: 62.6 MB, less than 40.35% of Java online submissions for Find K Closest Elements.
class Solution {
public List<Integer> findClosestElements(int[] arr, int k, int x) {
if (arr == null) {
return new ArrayList<>();
}
// It's possible that x is not in the array
// Find the insertion index of x in array -> find the 1st index where arr[index] >= x
int insertionIndex = findIndex(arr, x);
int left = insertionIndex - 1, right = insertionIndex;
while (k > 0) {
int leftDiff = left >= 0 ? x - arr[left] : Integer.MAX_VALUE;
int rightDiff = right < arr.length ? arr[right] - x : Integer.MAX_VALUE;
if (leftDiff <= rightDiff) {
left--;
} else {
right++;
}
k--;
}
// 1,2,3,4,5 x = 3 -> insertinIndex = 2, k = 4
// l r
// l r k = 3
// l r k = 2
// l r k = 1
//l r k = 0
List<Integer> res = new ArrayList<>();
for (int i = left + 1; i < right; i++) {
res.add(arr[i]);
}
return res;
}
private int findIndex(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) {
start = mid + 1;
} else {
end = mid;
}
}
if (arr[start] >= x) {
return start;
}
if (arr[end] >= x) {
return end;
}
// All elements are smaller than x, insert to the end of the array
return arr.length;
}
}
No comments:
Post a Comment