C语言找出数组中的特定元素的算法解析
问题描述:一个int数组,里面数据无任何限制,要求求出所有这样的数a[i],其左边的数都小于等于它,右边的数都大于等于它。能否只用一个额外数组和少量其它空间实现。
思路:如果能用两个辅助数组,那么相对来说简单一点,可定义数组Min和数组Max,其中Min[i]表示自a[i]之后的最小值(包括a[i]),Max[i]表示自a[i]之前元素的最大值。有了这两个辅助数组后,对于a[i],如果它大于Max[i-1]并且小于Min[i+1],那么就符合要求。
但是题目要求是只用一个额外数组,其实Max数组可以省去,完全可以边判断边计算,这是因为Max[i]是自左往右计算的,而判断时也是自左往右,两个过程正好可以合起来。只需用一个变量Max保存一下当前的最大值即可。下面给出两种方法的代码实现。
参考代码:
//函数功能:找元素 //函数参数:pArray指向数组,len为数组的元素个数 //返回值:无 voidFindElements_Solution1(int*pArray,intlen) { if(pArray==NULL||len<=0) return; int*pMin=newint[len]; int*pMax=newint[len]; inti; pMax[0]=pArray[0]; for(i=1;i<len;i++)//计算自i往前最大值的辅助数组 pMax[i]=(pMax[i-1]>=pArray[i])?pMax[i-1]:pArray[i]; pMin[len-1]=pArray[len-1]; for(i=len-2;i>=0;i--)//计算自i开始最小值的辅助数组 pMin[i]=(pMin[i+1]<=pArray[i])?pMin[i+1]:pArray[i]; if(pArray[0]<=pMin[0])//检查第1个元素是否满足条件 cout<<pArray[0]<<''; for(i=1;i<len-1;i++) { if(pArray[i]>=pMax[i-1]&&pArray[i]<=pMin[i+1])//满足这个关系式的元素符合要求 cout<<pArray[i]<<''; } if(pArray[len-1]>=pMax[len-1])//检查第len个元素是否满足条件 cout<<pArray[i]; cout<<endl; delete[]pMin; delete[]pMax; pMin=pMax=NULL; }
voidFindElements_Solution2(int*pArray,intlen) { if(pArray==NULL||len<=0) return; int*pMin=newint[len]; intMax; inti; Max=pArray[0]; pMin[len-1]=pArray[len-1]; for(i=len-2;i>=0;i--)//计算自i开始最小值的辅助数组 pMin[i]=(pMin[i+1]<=pArray[i])?pMin[i+1]:pArray[i]; if(pArray[0]<=pMin[0])//检查第1个元素是否满足条件 cout<<pArray[0]<<''; for(i=1;i<len-1;i++) { if(pArray[i]>=Max&&pArray[i]<=pMin[i+1])//满足这个关系式的元素符合要求 cout<<pArray[i]<<''; Max=(Max<pArray[i])?pArray[i]:Max;//更新当前最大值 } if(pArray[len-1]>=Max)//检查第len个元素是否满足条件 cout<<pArray[i]; cout<<endl; delete[]pMin; pMin=NULL; }
找出数组中两个只出现一次的数字(数组)
问题描述:一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。
思路:如果只有一个数字只出现一次,而其他都出现两次,则直接将所有数字做一次异或运算即可,因为相等的数字异或一下结果为0。如果有两个数字只出现一次,而其他数字出现了两次。该怎么办呢?《编程之美》一书提供了一种方法,即先将所有数字做一次异或运算,得到一个数字,然后以该数字的某非0位作为过滤位,将数组分成两个部分,此时只出现一次的数字会被分到不同的部分。现在问题就转为只出现一次的情况,对每部分分别做异或运算即可。
参考代码:
//函数功能:找出数组中两个只出现一次的数字 //函数参数:arr为源数组,len为数组元素个数,result用来存放结果 //返回值:无 voidFindIsolateTwo(int*arr,intlen,int*result) { inti,all=0,flag=1; for(i=0;i<len;i++)//所有数异或 all^=arr[i]; while(!(all&flag))//寻找过滤位 flag<<=1; result[0]=result[1]=0; for(i=0;i<len;i++)//利用过滤位区分 { if(flag&arr[i]) result[0]^=arr[i]; else result[1]^=arr[i]; } }