posts - 183,  comments - 10,  trackbacks - 0

两个指针的作用

两个指针一般用在一个序列中。
在一个序列中处理问题时,如果只使用一个指针,可能会造成双重循环的问题,结果时间复杂度会是 O(N) 。
如果采用两个指针可以很好地解决问题,时间复杂度也可以得到改进。

采用两个指针的例子很多,这里举几个:
1.
自动文摘中,如果采用循环查找的方法,时间复杂度是幂次方。采用两个指针,分别指向文摘的开始处和结束处可以在 O(N) 的时间复杂度内找到文摘。

2.
求连续数字之和等于一给定数,例如给定数是 15 ,则结果有 1 2 3 4 5、4 5 6、7 8 三种结果。
如果采用循环的方法事件复杂度是 O(N^2)
可以采用两个指针,分别指向 small 和 big 。当 sum(small ... big) 大于给定数时,small 指针右移,当 sum 小于给定数时,big 指针右移。直到 small 是给定数的一半时。

3.
调整数组,是前半部分是某种类型的数,后半部分是某种类型的数。
比如前半部分是奇数,后半部分是偶数
前半部分是负数,后半部分是非负数
采用两个指针,分别从左右两端进行扫描,检测,如果符合条件则交换两数,直到两个指针交叉为止。

4.
求一个数组中两个数的和等于一定数。
先对数组排序
然后从数组两端用两个指针扫描,检测,直到两个指针交叉为止。

当一个指针无法很好解决问题时,应该再增添一个指针,多一个帮手。

posted on 2011-09-13 13:12 unixfy 阅读(194) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理