注册 登录
编程论坛 数据结构与算法

O(n)时间复杂度求解:只有0和1的数组中两个位置间的0和1相等的所有位置

wenxinwukui 发布于 2011-06-09 20:22, 538 次点击
题目是这样的,在一个数组中只有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 编辑 ]
2 回复
#2
ZaakDov2011-06-10 01:59
首先,复杂度不可能是O(n)
而是O(n^2)
因为给你一组0,1,0,1,0,1,0,1,0,1......,0,1
光答案就有O(n^2)个,输出都要那么多

假设长度是n
for(delt[0]=0,i=1;i<=n;i++) delt[i]+=delt[i-1]+(a[i-1]?1:-1);
for(i=0;i<=2*n;i++) headg[i]=-1;
for(i=0;i<=n;i++){
    l[i]=headg[delt[i]+n];
    headg[delt[i]+n]=i;
}
for(i=0;i<=2*n;i++){
    for(k=0,j=headg[i];~headg[i];k++,j=l[i]) q[k]=j;
    for(j=0;j<k;j++) for(l=j+1;l<k;l++) printf("(%d,%d) ",q[j],q[l]);
}
printf("\n");

#3
wenxinwukui2011-06-10 09:42
回复 2楼 ZaakDov
谢谢。这个题是一个面试题,我当时写出来了O(n^2)的算法,不过面试官说有O(n)的让我想,我没有想出来,所以在这求教各位了。
1