问题描述:一个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为数组的元素个数 //返回值 : 无 void FindElements_Solution1(int *pArray, int len) { if(pArray == NULL || len <= 0 ) return ; int *pMin = new int[len]; int *pMax = new int[len]; int i; 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; }
void FindElements_Solution2(int *pArray, int len) { if(pArray == NULL || len <= 0 ) return ; int *pMin = new int[len]; int Max; int i; 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; }
本人享有博客文章的版权,转载请标明出处 http://blog.csdn.net/wuzhekai1985