|
|
亲！马上注册或者登录会查看更多内容！
您需要 登录 才可以下载或查看，没有帐号？立即注册
x
本帖最后由 Sophia 于 3-22-2016 02:02 PM 编辑 1 X3 w5 T; m. x4 ^: L$ H
6 I* A# ~; a- x4 c, w/ w5 C) q( {刷题偶得，算不上很系统的总结。- a+ Q, i( `3 |9 j9 {
1. 如果给定一个数组，一维或者二维，要求做某些操作，比如说搜索某个值。如果时间要求是O(log N)，那就必须得从二分的方向思考。具体每次砍掉什么的一半，就要看O(log N)中的那个N指的是谁了。一个典型的题目就是median of two sorted array. O(log(M+N))。题目等价与在两个数组中搜索第K小的元素。K = （M+N）/2. 这道题解的核心就是每次从两个数组中选一个，砍掉其中K/2个元素。( o. x2 k. {. e6 V! Y
5 v+ {) l$ k4 s, W0 y
2. 如果在一个unsorted array/matrix中进行高效搜索，包括point query或者range query。要么建索引，比如hash table或者binary search tree，或者quad tree。要么就要把unsorted 变成 sorted。总之，数据必须变得有结构，才能进行高效操作，否则，就得用暴力解法了。+ M7 X8 F8 @4 `' r! ]
g7 |, N0 Z9 z: B/ a1 M一点小总结。如有不对，欢迎大家指正。多谢！) ^! l9 l3 n0 V( u( |" _2 B
$ U( d6 V0 I$ R8 X2 c大家继续加油！* F7 i, n( U/ [' b
7 N2 `: q E# {8 T |
评分
-
查看全部评分
|
发表于 3-21-2016 05:47 PM
发表于 3-21-2016 05:47 PM
