P****e
发帖数: 56 | 1 也有可能是我没刷到。
有一个class叫Searcher. 你要写其中两个function: preProcessData, search.
preProcessData takes in an array of positive integers, all unique, and you
can do whatever you want with the array (modify it, sort it, create another
data structure in this class to store its content, etc). And there's no
restriction on space or time complexity.
search takes in 2 integers, x,y. x and y are both in the original array. and
it must return the total number of elements in the array that are between x
and y, exclusive. But must do it in O(1) time.
Example:
array = [2,4,9,5,7,3]
preProcessData (array) <- do whatever you want
search(2,7) <- 3 (3,4,5 are between 2 and 7, exclusive). in O(1) time. | v******s
发帖数: 144 | 2 在preprocess用O(nlog(n))把所有x,y (x < y) 都存起来不就行了。怎么会有这样的题 | v******s
发帖数: 144 | | p*********g
发帖数: 2998 | 4 这种题非常坑跌的， 最直观的做法就是2层for loop,把数字按照string, integer ,
字符和数量存进map,然后拿的时候久是o(1), 但你这么写，估计过不了， 肯定有更好
的办法， 可能会有follow up question | v******s
发帖数: 144 | 5 应该先排序 n(log(n)),然后数和排序后的index 存到hash就行
search时 index 相减 | G*****i
发帖数: 433 | 6 难道不就是记下每个数字的index，然后一减吗？ | J**9
发帖数: 835 | 7 Sort array
hash array (element --- index)
O(1) to get two indices | p**r
发帖数: 5853 | 8 LC至少有5道题和你的题基本一样，
只是稍微变种而已。
btw，这题也太简单了，
至少2种方法可以搞定。 | r*******y
发帖数: 270 | 9 改成x y不在array里也可以constant做 | l*3
发帖数: 2279 | 10 how？
【在 r*******y 的大作中提到】
: 改成x y不在array里也可以constant做
|
|
