解题笔记（27）――找数组中的特定元素 - wuzhekai的专栏 - 博客频道 - CSDN.NET

解题笔记（27）――找数组中的特定元素 - wuzhekai的专栏 - 博客频道 - CSDN.NET

问题描述：一个int数组，里面数据无任何限制，要求求出所有这样的数a[i]，其左边的数都小于等于它，右边的数都大于等于它。能否只用一个额外数组和少量其它空间实现。

      思路：如果能用两个辅助数组，那么相对来说简单一点，可定义数组Min和数组Max，其中Min[i]表示自a[i]之后的最小值（包括a[i]），Max[i]表示自a[i]之前元素的最大值。有了这两个辅助数组后，对于a[i]，如果它大于Max[i-1]并且小于Min[i+1]，那么就符合要求。

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;
}

Read full article from 解题笔记（27）――找数组中的特定元素 - wuzhekai的专栏 - 博客频道 - CSDN.NET