https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=503600
和LeetCode 4. Median of Two Sorted Arrays的思路非常像。
给一个排好序的N个不同数字,一个整数K,一个整数C,找到距离K第Cth近的数字,注意K并不一定出现在这个数组里例如数组是{1, 3, 5, 10, 20, 23} K = 11 C = 2,那么输出为5
复杂度:logN+logC
https://www.1point3acres.com/bbs ... read&tid=502523
再更正,我想错了,确实要两端找远的
和LeetCode 4. Median of Two Sorted Arrays的思路非常像。
给一个排好序的N个不同数字,一个整数K,一个整数C,找到距离K第Cth近的数字,注意K并不一定出现在这个数组里例如数组是{1, 3, 5, 10, 20, 23} K = 11 C = 2,那么输出为5
复杂度:logN+logC
https://www.1point3acres.com/bbs ... read&tid=502523
不知道为什么要iterative。target第Cth近的一定是头或者尾。哪个和target的差距越大就是那个。
如果数组是
- 1 2 4 找跟2第三个最近的元素, BS找到了[0],那么一定在1 和 4 里。发现4-2>2-1所以应该是4。
- 1 2 3 找跟2第三个最近的元素, BS找到了[0],那么一定在1 和 3 里。发现3-2==2-1所以再根据面试官的要求返回那个。
再更正,我想错了,确实要两端找远的
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.
Approach #2 Using Binary Search and Two Pointers
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);
}
}