找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 2507|回复: 6
收起左侧

[面经总结] 关于解数组类题目两个小技巧

[复制链接]

5

主题

2

精华

67

积分

资深会员

Rank: 2

积分
67
发表于 3-21-2016 05:47 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

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

评分

参与人数 1金钱 +3 收起 理由
Sophia + 3 给您点个赞!大米满满送上!

查看全部评分

1161

主题

184

精华

3664

积分

神级会员

Rank: 7Rank: 7Rank: 7

积分
3664
发表于 3-21-2016 05:47 PM 来自美国米群网手机版 | 显示全部楼层
感谢chicagoloop分享~~~

781

主题

575

精华

5670

积分

顶级版主

Rank: 9Rank: 9Rank: 9

积分
5670

活跃会员热心会员优秀版主

发表于 3-22-2016 03:49 PM | 显示全部楼层
给您点个赞!大米满满送上!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表