21xrx.com
2024-09-20 00:35:49 Friday
登录
文章检索 我的文章 写文章
C++编程实践：求长度为n的序列的最大值和最小值
2023-07-08 10:05:59 深夜i     --     --
C++编程 实践 序列 最大值 最小值

在C++编程领域，求解长度为n的序列的最大值和最小值是一个非常基础而又常见的问题。这个问题虽然看起来很简单，但是在算法实现和代码优化上还是需要花费一些时间和精力的。

首先，我们可以采用最朴素的方法，即遍历整个序列，记录当前最大值和最小值，这样可以得到序列的最大值和最小值。代码实现如下：



#include<bits/stdc++.h>


using namespace std;


int main()


{


  int n;


  cin>>n;


  int maxn=-1000000000,minn=1000000000;


  for(int i=1;i<=n;i++)


  {


    int x;


    cin>>x;


    maxn=max(maxn,x);


    minn=min(minn,x);


  }


  cout<<maxn<<" "<<minn<<endl;


  return 0;


}

这段代码看起来很简单，但是时间复杂度却是O(n)，当n很大时，计算量也会非常大。为了提高效率，我们可以采用分治法，将序列分为两部分，在两部分中求得最大值和最小值，最后再将两部分的结果合并，得到整个序列的最大值和最小值。代码实现如下：



#include<bits/stdc++.h>


using namespace std;


const int MAXN=100000;


int a[MAXN+5];


struct node


  int maxnans;


node solved(int l,int r)


{


  if(l==r) //边界情况


  {


    ans.maxn=a[l];


    ans.minn=a[l];


    return ans;


  }


  int mid=(l+r)/2;


  node left=solved(l,mid);


  node right=solved(mid+1,r);


  ans.maxn=max(left.maxn,right.maxn);


  ans.minn=min(left.minn,right.minn);


  return ans;


}


int main()


{


  int n;


  cin>>n;


  for(int i=1;i<=n;i++)


    cin>>a[i];


  node result=solved(1,n);


  cout<<result.maxn<<" "<<result.minn<<endl;


  return 0;


}

该算法的时间复杂度是O(nlogn)，效率会比最朴素的方法高很多。

最后，我们需要注意的是，对于一些特定的序列，我们还可以采用其他的算法，例如堆排序、归并排序等。因此，在实际应用中，我们需要根据情况灵活选择不同的算法。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复