Redian新闻
>
Eddie Bauer semi annual sale
avatar
Eddie Bauer semi annual sale# Living
c*u
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。
avatar
o*n
2
天天查,百分比每天都在降,就是没自己case的消息。心情浮躁,干脆不查了。
avatar
s*n
4
普通解法就是binary search 吧, 找到离这个target的左右邻居, 比较下就行。
更快是不是bucket idea, 分成[0,1), [1,2) [2,3), 假如太细的话, 可以多层, 然
后每个bucket里面是有序的double list.
avatar
t*6
5
同病相怜啊!当刷屏成为一种习惯,还是戒掉的好。
avatar
c*u
6
貌似数组中即使有duplicated number也不会怎样,仍旧可以使用传统的binary search

【在 s*******n 的大作中提到】
: 普通解法就是binary search 吧, 找到离这个target的左右邻居, 比较下就行。
: 更快是不是bucket idea, 分成[0,1), [1,2) [2,3), 假如太细的话, 可以多层, 然
: 后每个bucket里面是有序的double list.

avatar
s*k
7
co

【在 o*****n 的大作中提到】
: 天天查,百分比每天都在降,就是没自己case的消息。心情浮躁,干脆不查了。
avatar
M*6
8
产生buckets不是需要O(n)?
[在 sunvssoon (sunvssoon) 的大作中提到:]
:普通解法就是binary search 吧, 找到离这个target的左右邻居, 比较下就行。
:更快是不是bucket idea, 分成[0,1), [1,2) [2,3), 假如太细的话, 可以多层, 然
:后每个bucket里面是有序的double list.
avatar
g*o
9
同病相怜啊!共勉!
avatar
e*s
10
怎么query bucket呢.

【在 s*******n 的大作中提到】
: 普通解法就是binary search 吧, 找到离这个target的左右邻居, 比较下就行。
: 更快是不是bucket idea, 分成[0,1), [1,2) [2,3), 假如太细的话, 可以多层, 然
: 后每个bucket里面是有序的double list.

avatar
l*3
11
10/15 TSC RD
还在等,早戒了,连uscis都戒了
avatar
c*t
12
感觉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) {

avatar
a*y
13
我噻,您这个可真够久的。同情啊。希望您早日收到好消息。

【在 l*******3 的大作中提到】
: 10/15 TSC RD
: 还在等,早戒了,连uscis都戒了

avatar
r*n
14
很久前面O记问到过这道题,答曰:数组中的数减去target的值然后找出绝对值最小的
即可
avatar
S*4
15
can not agree more!
avatar
a*g
16
唯一的陷阱就是写binary search的时候注意一下跳出条件吧。这题怎么能比logn强?
我很好奇。
avatar
S*a
17
me too.

【在 o*****n 的大作中提到】
: 天天查,百分比每天都在降,就是没自己case的消息。心情浮躁,干脆不查了。
avatar
c*u
18
我当时就说如果数组是排好序的数组,里面的元素没什么特征,那么最好只能是log n
。然后我说肯定有trap,于是跳出binary search后我做了越界等检查,也注意了全程
使用double类型。
后来想了想,即使数组中有重复元素,还是要用binary search。

【在 a*******g 的大作中提到】
: 唯一的陷阱就是写binary search的时候注意一下跳出条件吧。这题怎么能比logn强?
: 我很好奇。

avatar
m*a
19
同戒
avatar
a*g
20
最好的结果就是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。

avatar
y*1
21
bless

【在 l*******3 的大作中提到】
: 10/15 TSC RD
: 还在等,早戒了,连uscis都戒了

avatar
S*C
22
//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怎么做?
avatar
c*e
23
handshake
avatar
D*i
24
幸福就是善于等待
共勉
avatar
G*D
25
co
avatar
s*n
26

我9月4号申请的今天才拿到

【在 a*****y 的大作中提到】
: 我噻,您这个可真够久的。同情啊。希望您早日收到好消息。
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。