c*****u
发帖数: 867 | 1 我和同学被两家不同的公司考了这个题。
输入是一个排好序的decimal数组和一个target number。要求找出这个数组中最接近
target的数。例子：
[1.0, 2.5, 3.0], target = 0.5, 那么就返回1.0.
[1.0, 2.5, 3.0], target = 2.0, 那么就返回2.5.
要求用Java写，函数的signature要我自己写，所以所有数字我都定义成double。我觉
得这就用普通的binary search吧？
int left = 0;
int right = len - 1;
while(left <= right) {
int mid = ...;
然后比较大小左右移动left和right
}
请问这道题的陷阱在哪里呢？既然他问的是decimal，而不是integer，那么应该有陷阱。
followup question是怎么能做到比O(lg n)更快。前提是函数只被call一次，不是多次
被call。 | s*******n
发帖数: 305 | 2 普通解法就是binary search 吧， 找到离这个target的左右邻居， 比较下就行。
更快是不是bucket idea, 分成[0,1), [1,2) [2,3), 假如太细的话， 可以多层， 然
后每个bucket里面是有序的double list. | c*****u
发帖数: 867 | 3 貌似数组中即使有duplicated number也不会怎样，仍旧可以使用传统的binary search
【在 s*******n 的大作中提到】
: 普通解法就是binary search 吧， 找到离这个target的左右邻居， 比较下就行。
: 更快是不是bucket idea, 分成[0,1), [1,2) [2,3), 假如太细的话， 可以多层， 然
: 后每个bucket里面是有序的double list.
| M***6
发帖数: 895 | 4 产生buckets不是需要O（n）？
[在 sunvssoon (sunvssoon) 的大作中提到：]
:普通解法就是binary search 吧， 找到离这个target的左右邻居， 比较下就行。
:更快是不是bucket idea, 分成[0,1), [1,2) [2,3), 假如太细的话， 可以多层， 然
:后每个bucket里面是有序的double list. | e*******s
发帖数: 1979 | 5 怎么query bucket呢.
【在 s*******n 的大作中提到】
: 普通解法就是binary search 吧， 找到离这个target的左右邻居， 比较下就行。
: 更快是不是bucket idea, 分成[0,1), [1,2) [2,3), 假如太细的话， 可以多层， 然
: 后每个bucket里面是有序的double list.
| c********t
发帖数: 5706 | 6 感觉bucket和hashtable预处理都要O(n) 理论上binary search是最快的。但是这个题
Trinary search 会不会快一些？ 选left=(begin+end)/3, right=2*(begin+end)/3,
然后比较看在target在三个区间哪里，再移动begin, end。但是每次选完 left和right
, 都有可能要compare two times, 所以会不会更快好像要证明一下。
【在 c*****u 的大作中提到】
: 我和同学被两家不同的公司考了这个题。
: 输入是一个排好序的decimal数组和一个target number。要求找出这个数组中最接近
: target的数。例子：
: [1.0, 2.5, 3.0], target = 0.5, 那么就返回1.0.
: [1.0, 2.5, 3.0], target = 2.0, 那么就返回2.5.
: 要求用Java写，函数的signature要我自己写，所以所有数字我都定义成double。我觉
: 得这就用普通的binary search吧？
: int left = 0;
: int right = len - 1;
: while(left <= right) {
| r****n
发帖数: 63 | 7 很久前面O记问到过这道题，答曰：数组中的数减去target的值然后找出绝对值最小的
即可 | a*******g
发帖数: 1221 | 8 唯一的陷阱就是写binary search的时候注意一下跳出条件吧。这题怎么能比logn强？
我很好奇。 | c*****u
发帖数: 867 | 9 我当时就说如果数组是排好序的数组，里面的元素没什么特征，那么最好只能是log n
。然后我说肯定有trap，于是跳出binary search后我做了越界等检查，也注意了全程
使用double类型。
后来想了想，即使数组中有重复元素，还是要用binary search。
【在 a*******g 的大作中提到】
: 唯一的陷阱就是写binary search的时候注意一下跳出条件吧。这题怎么能比logn强？
: 我很好奇。
| a*******g
发帖数: 1221 | 10 最好的结果就是binary searchhttps://www.quora.com/Search-Algorithms-Why-cant-
there-be-an-algorithm-faster-than-binary-search
不过有一种叫interpolation search的利用插值，可以在数据均匀的情况下更快，但也
可能更慢。你可以设计一种新的算法，把binary search和interpolation search结合
起来。很插值，插几轮效果不好，就去binary.
n
【在 c*****u 的大作中提到】
: 我当时就说如果数组是排好序的数组，里面的元素没什么特征，那么最好只能是log n
: 。然后我说肯定有trap，于是跳出binary search后我做了越界等检查，也注意了全程
: 使用double类型。
: 后来想了想，即使数组中有重复元素，还是要用binary search。
| S*******C
发帖数: 822 | 11 //return the closet number
public double closestNumber(double[] nums, double target) {
if (nums == null || nums.length == 0) {
return -1;
}
int low = 0, high = nums.length - 1;
while (low < high) {
int mid = low + (high - low) / 2;
double diff1 = Math.abs(nums[mid] - target);
double diff2 = Math.abs(nums[mid + 1] - target);
if (diff1 >= diff2) {
low = mid + 1;
} else {
high = mid;
}
}
return nums[high];
}
follow up怎么做？ |
|
