算法设计与分析解题报告.ppt

算法设计与分析解题报告 零和区间问题 120327027 曾志鹏 2012.9.19 问题描述 问题分析 给定一组序列数4 -1 2 1 -2 -1 5，对每一个元素a[i]，求出sum(a[0]…a[i])，如果一个数字出现2次或者2次以上，假设第一次出现位置为i，第二次出现为j，可以得出sum(a[i+1]…a[j]) = 0。 即为一零和区间 算法设计 输入序列a[]： 4 -1 2 1 -2 -1 5 求和结果sum[]：4 3 5 6 4 3 8 从结果序列中求得maxValue = 8 定义数组b[]，设定b的大小为 size= 2 * maxValue + １ 对sum中的每一项，有b[sum[i]] = -1，考虑到sum[i]可能为负，将sum每一项加上绝对值最大的数maxValue 转换序列sum[]:12 11 13 14 12 11 16 并设定b[maxValue] = 0 初始化最大零和区间长度maxLength = 0 算法设计 转换序列sum[]:12 11 13 14 12 11 16 初始化的b[]为： 算法设计 算法设计 转换序列sum[]:12 11 13 14 12 11 16 最后结果序列为： 得出最大零和区间长度为4 算法补充 为何要设定b[maxValue] = 0 ? 假定输入序列为：0 0 0 0 0 求和序列为：0 0 0 0 0 计算 maxValue = 0 初始b如下，如果为设定b[0] = 0，第一轮结束如右图所示 核心代码 ????int?*temp?=?new?int[2?*?maxValue?+?1]; ?? //设置temp的大小 ????memset(temp,-1,(2?*?maxValue?+?1)?*?sizeof(int)); ?? //初始化temp ????temp[maxValue]?=?0; ?? //解决0 0 0 0和3 -1 -2 5类似序列 ????for?(i?=?1;?i?<=?n;?i++) ?? ????{ ?? ????????sum[i]?+=?maxValue; ?? //每一项加上最大值 ????????if?(temp[sum[i]]?!=?-1) ?? //该元素已经出现过 ????????{ ?? ????????????if?(abs(i?-?temp[sum[i]])?>?MAX_LENGTH) ?? ????????????{ ?? ????????????????MAX_LENGTH?=?abs(i?-?temp[sum[i]]); //计算最大区间?? ????????????} ?? ????????????if?(abs(i?-?temp[sum[i]])?<?MIN_LENGTH) ?? ????????????{ ?? ????????????????MIN_LENGTH?=?abs(i?-?temp[sum[i]]); ?? //计算最小区间 ????????????}??????? ?? ????????} ?? ????????else?? //该元素从未出现 ????????????temp[sum[i]]?=?i; ?? ????} 时间复杂度 时间复杂度：整个查找过程只需一次遍历，因此时间复杂度为O(n) 算法不足 当计算得到|maxValue|很大时 ?int?*temp?=?new?int[2?*?maxValue?+?1]; 将耗费大量空间 * * -1 16 -1 -1 -1 -1 -1 -1 -1 0 … -1 15 14 13 12 11 10 9 8 … 0 遍历sum数组if b[sum[i]] == -1 then b[sum[i]] = i 计算到b[3]=14时，数组元素如下 -1 16 -1 3 2 0 1 -1 -1 0 … -1 15 14 13 12 11 10 9 8 … 0 -1 16 -1 3 2 0 1 -1 -1 0 … -1 15 14 13 12 11 10 9 8 … 0 转换序列sum[]:12 11 13 14 12 11 16 计算到sum[4]=12时，b[12] != 0，即12已经出现过 计算2次出现的位置，begin=0，end=4，说明sum(a[1]…a[4]) = 0 即 maxLength = end-(begin+1)+1 = 4 5 16 -1 3 2 0 1 -1 -1 0 … -1 15 14 13 12 11 10 9 8 … 0 -1 -1 -1 -1 -1 -1 5 4 3 2 1 0 -1 -1 -1 -1 -1 0 5 4 3 2 1 0 最