打印本文   关闭窗口

C++实例(去除数组中的重复数字)

作者：佚名  文章来源：不详  点击数  更新时间：2008/10/22 21:33:57  文章录入：杜斌  责任编辑：杜斌

题目： 有一个数组t[100]，存放了1～99之间的数字，用效率较高的代码把重复数字去掉。例如数组{1,2,2,2,3,5,6,6}变成{1,2,3,5,6}。 　　×××××××××××××××××××××××××××××××××× 　　申请标志数组 　　此题重复的数字可能不只一个，上述求和的方法不行了。因为是高效率，我们可以采用空间换时间的策略来解决。 　　设立访问标志数字，初始化为0，访问到N时将标志数字的第N个元素置为N 　　最后遍历该数组，若标志数组中对应值为非0，则顺序存储该数字于原数组中，最后返回去除重复数字后的有效数的个数 　　int RemoveRep(int array[], int n) 　　{ 　　int *arrayflag = (int *)malloc(n*sizeof(int)); 　　int left = 0, i = 0; 　　while(i<n) 　　arrayflag[i++] = false; //初始化标志数组 　　for(i=0;i<n;i++)//剔除算法 　　{ 　　arrayflag[array[i]] = array[i]; //将出现过的数保存到对应的位置 　　} 　　for(i=0;i<n;i++) //取出有效数 　　{ 　　if(arrayflag[i] != false) 　　array[left++] = arrayflag[i]; 　　} 　　return left; 　　} 　　×××××××××××××××××××××××××××××××××× 　　符号标志法 　　上述方法的空间复杂度为O(N)，利用符号位作为标志即可不申请O(N)标志数组 　　int SignedRemoveRep(int array[], int n) 　　{ 　　int i,left = 0; 　　for(i=0;i<n;i++)//将出现过的位置置负号标志 　　{ 　　if(array[i] > 0) 　　array[array[i]] = -array[array[i]]; 　　else 　　array[-array[i]] = -array[-array[i]]; 　　} 　　for(i=0;i<n;i++)//抽取算法 　　{ 　　if(array[i] < 0) //根据标志顺序保存出现过的值 　　array[left++] = i; 　　} 　　return left; 　　} 　　×××××××××××××××××××××××××××××××××× 　　void main(void) 　　{ 　　int t[100]; 　　int i,j,left; 　　for(i=0;i<100;i++) //随机产生100个数字 　　{ 　　j = rand()%99+1; 　　t[i] = j; 　　printf("%d ",t[i]); 　　if(i%10 == 9) 　　printf("\n"); 　　} 　　//left = RemoveRep(t, 100); 　　left = SignedRemoveRep(t, 100); 　　for(i=0;i<left;i++) 　　{ 　　printf("%d ",t[i]); 　　if(i%10 == 9) 　　printf("\n"); 　　} 　　} 考试大论坛

打印本文   关闭窗口