ITPub博客

首页 > 应用开发 > IT综合 > 算法找数组中的特定元素

算法找数组中的特定元素

IT综合 作者:dongyu2013 时间:2014-05-17 09:52:00 0 删除 编辑

一个 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保存一下当前的最大值即可。下面给出两种方法的代码实现。

      参考代码:

  1. //函数功能 : 找元素  
  2. //函数参数 : pArray指向数组,len为数组的元素个数  
  3. //返回值 : 无  
  4. void FindElements_Solution1(int *pArray, int len)  
  5. {  
  6.     if(pArray == NULL || len <= 0 )  
  7.         return ;  
  8.   
  9.     int *pMin = new int[len];  
  10.     int *pMax = new int[len];  
  11.     int i;  
  12.   
  13.     pMax[0] = pArray[0];  
  14.     for(i = 1; i < len; i++)       //计算自i往前最大值的辅助数组  
  15.         pMax[i] = (pMax[i-1] >= pArray[i])? pMax[i-1]: pArray[i];  
  16.     pMin[len-1] = pArray[len-1];  
  17.     for(i = len - 2; i >= 0; i--) //计算自i开始最小值的辅助数组  
  18.         pMin[i] = (pMin[i+1] <= pArray[i])? pMin[i+1]: pArray[i];  
  19.   
  20.     if(pArray[0] <= pMin[0])     //检查第1个元素是否满足条件  
  21.         cout<' ';  
  22.     for(i = 1; i < len - 1; i++)  
  23.     {  
  24.         if(pArray[i] >= pMax[i-1] && pArray[i] <=pMin[i+1]) //满足这个关系式的元素符合要求  
  25.             cout<' ';  
  26.     }  
  27.     if(pArray[len-1] >= pMax[len-1]) //检查第len个元素是否满足条件  
  28.         cout<
  29.     cout<
  30.   
  31.     delete [] pMin;  
  32.     delete [] pMax;  
  33.     pMin = pMax = NULL;  
  34. }  
请登录后发表评论 登录
全部评论

注册时间:2013-12-25

  • 博文量
    263
  • 访问量
    209145