1 简介
补丁数组是一种数据结构,封装后可以像普通数组一样使用,效率又较高。
2 效率
假设N为数组长度,M为以前对数组增删的总次数
普通数组:
增/删:O(N);查:O(1)
链表:
增/删:O(1);查:O(N)
补丁数组:
增/删:O(M);查:O(M)
3 实现
假设封装后用户看到的数组为数组a[]。(方便起见,假设为整形数组)
开数组b[N]为实际储存数组;c[]为下标补丁数组;d[]为数据补丁数组。其中b.length=N,c.length和d.length需要大于增/删总次数。
3.1 增
假设在a[i]和a[i+1]中增加一个值为x。
1)c[]中增加一条数据:表示从i+1开始的所有下标,在a映射到b时全部-1。(如i=2之后查a[5],那么应取出b[4])
2)d[]中增加一条数据:表示a[i+1]的值为x,并且只计算了c[k]以前的偏移。(意味着:如果后来c[]又有新补丁数据,那么还得计算后面的)
3.2 删
假设删除a[i]。
1)c[]中增加一条数据:表示从i+1开始的所有下标,在a映射到b时全部+1。(如i=2之后查a[5],那么应取出b[6])
3.3 改
如正常数组。
3.4 查
假设查a[i]。假设最终取出b[j]
1)j=i;
2)遍历c[],适时地修改(就是+1/-1)j值。
4 样例
1)
语句:建立数组,N=8,并赋值
实现: a[]=[3,4,2,1,7,0,6,8]
b[]=[3,4,2,1,7,0,6,8]
c[]={}
d[]={}
2)
语句:删除a[1]
实现: a[]=[3,2,1,7,0,6,8]
b[]=[3,NULL,2,1,7,0,6,8]
c[]={“所有a[i]中i>=1的在查询时+1”}
d[]={}
3)
语句:增加a[3]和a[4]之间一个数为9
实现: a[]=[3,2,1,7,9,0,6,8]
b[]=[3,NULL,2,1,7,0,6,8]
c[]={“所有a[i]中i>=1的在查询时+1”,“所有a[i]中i>4的在查询时-1”}
d[]={“a[3]和a[4]之间的为9,而且此时计算的偏移只计算了c[0]和c[1]”}
4)
语句:查询a[2]
实现: a[]=[3,2,1,7,9,0,6,8]
b[]=[3,NULL,2,1,7,0,6,8]
c[]={“所有a[i]中i>=1的在查询时+1”,“所有a[i]中i>4的在查询时-1”}
d[]={“a[3]和a[4]之间的为9,而且此时计算的偏移只计算了c[0]和c[1]”}
执行算法:
j=2;
查看c[0]得:j=3;
查看c[1]得:j=3;
读取b[3]得:a[2]=1;
5 用途
适用于同时需要 增删 和 改查 的地方。当N很大,增删较少时有优势。
补丁数组(增删改查都较快的数组)