f******t
发帖数: 7283 | 1 给一串数字（比如说1，4，10，22，30，表示4个区间：[1，4]，（4，10]，（10，22]
，（22，30]）。现在给很多个数字，要设计一个快速算法，能用最快的速度告诉那些
数字分别落在哪个bucket那里。比如说前面这个例子输入double数13，算法返回string
,30]"
当然最容易想到的是对于每个输入的数字，都做一个for loop把区间都扫一遍，找到合
适的为止；但这样输入N个数字的时候就要做N次for loop。有没有更好的算法，在输入
是大批量数字的情况下速度比每个数字都要做一次for loop的算法要快呢？ | S**I
发帖数: 15689 | 2 sort the input array, then scan once is enough.
22]
string
【在 f******t 的大作中提到】
: 给一串数字（比如说1，4，10，22，30，表示4个区间：[1，4]，（4，10]，（10，22]
: ，（22，30]）。现在给很多个数字，要设计一个快速算法，能用最快的速度告诉那些
: 数字分别落在哪个bucket那里。比如说前面这个例子输入double数13，算法返回string
: ,30]"
: 当然最容易想到的是对于每个输入的数字，都做一个for loop把区间都扫一遍，找到合
: 适的为止；但这样输入N个数字的时候就要做N次for loop。有没有更好的算法，在输入
: 是大批量数字的情况下速度比每个数字都要做一次for loop的算法要快呢？
| f******t
发帖数: 7283 | 3 能不能详细说说呢？比如说就拿我前面举的那个例子。
【在 S**I 的大作中提到】
: sort the input array, then scan once is enough.
:
: 22]
: string
| f***i
发帖数: 162 | 4 在你的例子中就把13,8,25 sort一下变成8,13,25
然后从8开始在区间数组中search,找到了search就13,然后25....因为input数组是排序
过的,所以肯定先搜到8然后13然后25
【在 f******t 的大作中提到】
: 能不能详细说说呢？比如说就拿我前面举的那个例子。
| f******t
发帖数: 7283 | 5 这个方法对于小数据量是有改善作用的。可能前面我没有说清楚，interviewer给的前
提是数据量大概是几百万到几千万个数字这样的array，这么巨大的array搞排序估计得
不偿失啊。
bucket的数量不多，大概几个到十来个；但是需要找bucket的数字很多，有几百万到上
千万个。
【在 f***i 的大作中提到】
: 在你的例子中就把13,8,25 sort一下变成8,13,25
: 然后从8开始在区间数组中search,找到了search就13,然后25....因为input数组是排序
: 过的,所以肯定先搜到8然后13然后25
| s****o
发帖数: 19 | 6 preprocess your buckets to create such a hash table:
2, 3, 4 -> (1,4]
5, 6, ..., 10 -> (4, 10]
11, 12, ..., 22 -> (10, 22]
23, 24, ..., 30 -> (22, 30]
Then for each incoming number, check if it is a key in the hash table, if it
is, return the value. If it is not, then comare it with 1, if it <= 1,
return (negative infinity, 1], otherwise return (30, positive infinity)
【在 f******t 的大作中提到】
: 这个方法对于小数据量是有改善作用的。可能前面我没有说清楚，interviewer给的前
: 提是数据量大概是几百万到几千万个数字这样的array，这么巨大的array搞排序估计得
: 不偿失啊。
: bucket的数量不多，大概几个到十来个；但是需要找bucket的数字很多，有几百万到上
: 千万个。
| c*********n
发帖数: 1371 | 7 我觉得这个题的本质是在第一个数组A中，对第二个数组B中的每个
元素找最接近的两个数：
假设对space没有要求.
create arrays:
BLower[B.length]{int.minValue, ........},
BUpper[B.length]{int.maxValue, ........}
for each( a in A){
for( i from 0 to B.length-1)
{
if(a
BLower[i]=a;
}
if(a>B[i] && BUpper[i]>a){
BUpper[i]=a;
}
}
}
return string[]{"[BLower[0], BUpper[0]", "[BLower[1], BUpper[1]",....."[
BLower[n-1], BUpper[n-1]"}
22]
string
【在 f******t 的大作中提到】
: 给一串数字（比如说1，4，10，22，30，表示4个区间：[1，4]，（4，10]，（10，22]
: ，（22，30]）。现在给很多个数字，要设计一个快速算法，能用最快的速度告诉那些
: 数字分别落在哪个bucket那里。比如说前面这个例子输入double数13，算法返回string
: ,30]"
: 当然最容易想到的是对于每个输入的数字，都做一个for loop把区间都扫一遍，找到合
: 适的为止；但这样输入N个数字的时候就要做N次for loop。有没有更好的算法，在输入
: 是大批量数字的情况下速度比每个数字都要做一次for loop的算法要快呢？
| f******t
发帖数: 7283 | 8 这个算法只能应付数字是整数的情况，题目的条件里数字可以是小数，bucket的上下限
也都有可能是小数......
it
【在 s****o 的大作中提到】
: preprocess your buckets to create such a hash table:
: 2, 3, 4 -> (1,4]
: 5, 6, ..., 10 -> (4, 10]
: 11, 12, ..., 22 -> (10, 22]
: 23, 24, ..., 30 -> (22, 30]
: Then for each incoming number, check if it is a key in the hash table, if it
: is, return the value. If it is not, then comare it with 1, if it <= 1,
: return (negative infinity, 1], otherwise return (30, positive infinity)
| f******t
发帖数: 7283 | 9 这个算法里，两重for loop下来，循环的次数还是跟我原贴里的算法一样多啊。
假设bucket的数量有M个，有N个实数需要处理，这个题目interviewer的本意是看能不
能给出一个算法，它不需要进行M*N次比较大小的操作。
【在 c*********n 的大作中提到】
: 我觉得这个题的本质是在第一个数组A中，对第二个数组B中的每个
: 元素找最接近的两个数：
: 假设对space没有要求.
: create arrays:
: BLower[B.length]{int.minValue, ........},
: BUpper[B.length]{int.maxValue, ........}
: for each( a in A){
: for( i from 0 to B.length-1)
: {
: if(a
| c******o
发帖数: 534 | 10 hashtable查找不也是要算hash code，严格来说也不是 O（1）
【在 f******t 的大作中提到】
: 这个算法只能应付数字是整数的情况，题目的条件里数字可以是小数，bucket的上下限
: 也都有可能是小数......
:
: it
| S**I
发帖数: 15689 | 11 If all elements are integers, then the hash table size is the same as
summation of size of all buckets. If number of buckets is small and the
input array is huge, then lookup is O(1).
【在 c******o 的大作中提到】
: hashtable查找不也是要算hash code，严格来说也不是 O（1）
| f******t
发帖数: 7283 | 12 现在题目要求的是处理包括小数在内的情况。有没有比O(N)算法更快的呢？
【在 S**I 的大作中提到】
: If all elements are integers, then the hash table size is the same as
: summation of size of all buckets. If number of buckets is small and the
: input array is huge, then lookup is O(1).
| S**I
发帖数: 15689 | 13 I don't think it can be faster than O(n).
【在 f******t 的大作中提到】
: 现在题目要求的是处理包括小数在内的情况。有没有比O(N)算法更快的呢？
| S**I
发帖数: 15689 | 14 sort the buckets first, then N*logM is enough.
【在 f******t 的大作中提到】
: 这个算法里，两重for loop下来，循环的次数还是跟我原贴里的算法一样多啊。
: 假设bucket的数量有M个，有N个实数需要处理，这个题目interviewer的本意是看能不
: 能给出一个算法，它不需要进行M*N次比较大小的操作。
|
|
