编写一个程序，求一个整数数组中最大元素和次大的元素。

[问答题]

推荐

赞花婆

设计函数fun用于求一个整数数组中最大元素和次大的元素，为了能改变实参的值，函数形参设计为引用型参数。程序如下：

#include <stdio.h>
void fun(int a[ ],int n,int &maxp1,int &maxp2)
{
    int i;
    if (a[0]<a[1])
    {    maxp1=a[1];
       maxp2=a[0];
}
else
{    maxp1=a[0];
    maxp2=a[1];
}
for (i=2;i<n;i++ )
    if (a[i]>maxp1)
    {    maxp2=maxp1;
       maxp1=a[i];
    }
}
void main()
{
    int a[ ]={0,2,5,6,8,1,3,4,7,9},max1,max2;
    int n=10;
    fun(a,n,max1,max2);
    printf("MAX1:%d,MAX2:%d\n",max1,max2);
}

发表于 2018-05-07 10:53:10 回复(0)

xuminxiang

可以用分治法做

思路：将原表分成左右子表，分别找出各自的最大和次大元素，然后进行简单选择即可

// 定义无穷大值
#define INF 32768

void solve (int a[], int low, int high, int &max1, int &max2)
{
    if (high == low) {
        max1 = a[low];
        max2 = -INF;
    } else if (high - low == 1) {
        max1 = max(a[low], a[high]);
        max2 = min(a[low], a[high]);
    } else {
        int lmax1, lmax2, rmax1, rmax2;
        int mid = (low + high) / 2;
        
        solve(a, low, mid, lmax1, lmax2);
        solve(a, mid + 1, high, rmax1, rmax2);
        max1 = max(lmax1, rmax1);
        if (max1 == lmax1)
            max2 = max(lmax2, rmax1);
        else 
            max2 = max(lmax1, rmax2);
    }
}

对应递推式：T(n) = 2T(n/2) + C --->>> 时间复杂度为O(n)

发表于 2020-08-02 15:47:01 回复(0)

芨荠

#include<stdio.h>

void fun(int *p,int *max1,int *max2){
    int *q = p;
    *max1 = *max2 = *p;
    while(*p){
        if(*p>*max1) *max1 = *p;
        p++;
    }
    while(*q){
        if(*q>*max2 and *q!=*max1) *max2 = *q;
        q++;
    }
}

int main(){
    int s[]={21,3,1,14,6,2};
    int max1,max2;
    fun(s,&max1,&max2);
    printf("%d+%d=%d",max1,max2,max1+max2);
}

发表于 2018-09-08 13:54:21 回复(0)

提交观点

问题信息

C++

上传者：赞花婆

难度：

3条回答 3收藏 1148浏览

编写一个程序，求一个整数数组中最大元素和次大的元素。

问题信息

热门推荐

相关试题