《巧用数组下标 轻松回避重复判断》由会员分享，可在线阅读，更多相关《巧用数组下标 轻松回避重复判断（5页珍藏版）》请在金锄头文库上搜索。
1、巧用数组下标巧用数组下标 轻松回避重复判断轻松回避重复判断时间：2009.02.02 目标：引导拓展思路、不同角度思考问题 提示：有意识的培养发散思维在程序设计的某个环节中，需要统计不同数据的个数，按照常规思路的算法简单描述如下：读入下一个数；将该数与之前已读入的数一一比较，如果都不同，则该数是新数，累加器加 1；否则，表示该数是旧数，有重复，直接退出比较的循环。是否读完所有数据，如果是，输出累加器值，结束；否则，转到；下面用一个实例说明。例产生 10 个范围为 120 的随机整数，统计不同数的个数。按照常规思路，得如下参考程序。program tongji(input,output);var
2、a:array1.10 of integer;i,j,t:integer;beginwriteln(产生随机数:);randomize;for i:=1 to 10 dobegin ai:=1+random(19); write( ,ai); end;t:=0;for i:=1 to 10 dobeginj:=1;while (jaj) do j:=j+1;if j=i then t:=t+1;end;writeln; writeln(统计不同数据有,t,个.);end.由以上程序可知，完成数据统计需要两重循环，时间复杂度为O(n2)。如果数据是正整数，那么试着换另外一种思路：将数据作为数组的
3、下标，进行一个赋值为 1 的标记操作。比如，现有数：2，6，2，用数组 b辅助存储，依次操作：b2:=1，b6:=1，接下来是 2，已重复，在程序中无需特殊判断，执行相同操作：b2:=1，这样就可以有效回避重复判断，最后只要累计 b数组中值为 1的个数，事实上，数组中其他元素由于没有进行赋值操作，保留了默认值 0，因此累加操作也可以扩展到所有数组元素的直接相加，为了更有效的累加，可以在执行赋值操作时，加入数据范围的上限、下限标识：max 和 min，每读入一个数后，更新数据范围，最后只要将下标为上下限范围的数组数据进行累加。参考程序如下：program tongji(input,output)
4、;vara:array1.10 of integer;b:array1.20 of integer;i,t,max,min:integer;beginwriteln(产生随机数:);randomize;for i:=1 to 10 do 产生 10 个(1-20)随机数begin ai:=1+random(19); write( ,ai); end;t:=0; max:=0; min:=10000; 设置统计时，数组范围的上下标识for i:=1 to 10 dobeginbai:=1; 将数据以数组下标的形式写入，避免判断if aimax then max:=ai; 更新数组范围的上下标识if aimax then max:=ai; if ai0 thenbegin write(i,:,bi , ); t:=t+1; end; 统计不同数据个数writeln; writeln(t);时间复杂度由原来的 O(n2)降低为 O(n)。编程时，不妨抛开传统解题思路，尝试着用其他方法解决，一个小小的数据统计程序，或许可以给你些许启迪，愿本文起到抛砖引玉的作用。
