| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 534 人关注过本帖
标题:O(n)时间复杂度求解:只有0和1的数组中两个位置间的0和1相等的所有位置
取消只看楼主 加入收藏
wenxinwukui
Rank: 1
等 级:新手上路
帖 子:22
专家分:6
注 册:2010-11-15
收藏
 问题点数:0 回复次数:1 
O(n)时间复杂度求解:只有0和1的数组中两个位置间的0和1相等的所有位置
题目是这样的,在一个数组中只有0和1,要求输出所有的相邻的0和1数目相同的区间的起始位置,时间复杂度尽量好(要求是O(n))
例如:
数组a:{0,1,1,1,0,0,1,0}
输出:(0, 1)   (0, 5)   (0, 7)   (2, 5)   (2, 7)   (3, 4)   (3, 6)   (5, 6)   (6, 7)  (输出的先后顺序可能不同)
结果(0,5)表示a[0]和a[5]间0和1的数目相等都为3.

[ 本帖最后由 wenxinwukui 于 2011-6-9 20:32 编辑 ]
2011-06-09 20:22
wenxinwukui
Rank: 1
等 级:新手上路
帖 子:22
专家分:6
注 册:2010-11-15
收藏
得分:0 
回复 2楼 ZaakDov
谢谢。这个题是一个面试题,我当时写出来了O(n^2)的算法,不过面试官说有O(n)的让我想,我没有想出来,所以在这求教各位了。
2011-06-10 09:42
快速回复:O(n)时间复杂度求解:只有0和1的数组中两个位置间的0和1相等的所有位置 ...
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.011905 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved