给出一个分治算法来找出n个元素序列中第2大的元素

2021年9月16日 2点热度 0条评论 来源: little pepper

题目:给出一个分治算法来找出n个元素序列中的第2大的元素。

如果不是题目要求用分治法,用遍历或排序都比这个分治法要快。下面说说解题思路吧

解题思路:当序列A[1..n]中元素的个数n=2时,通过直接比较即可找出序列的第2大元素。当n>2时,先求出序列A[1..n-1]中的第1大元素x1和第2大元素x2;然后,通过2次比较即可在三个元素x1,x2和A[n]中找出第2大元素,该元素即为A[1..n]中第2大元素。

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

int a[100];
int n;

int max;   //当前最大元素 
int f(int n)  
{
	int min;   //当前最小元素 
	if(n==2)     //只有两个元素时,直接求解(最小问题) 
	{
		if(a[n-2]>a[n-1])
			max=a[n-2],min=a[n-1];
		else
			max=a[n-1],min=a[n-2]; 
		return min;
	}
	else
	{ 
		min=f(n-1);		//递归找第二大元素 
		if(a[n-1]>max) min=max,max=a[n-1];   //找到前面n-1个元素中最大和第二大元素时
		if(a[n-1]<max&&a[n-1]>min) min=a[n-1]; //再与第n个元素比较找第二大元素 
		return min;   //返回结果 
	}
}

void random() 
{
	srand(time(NULL));
	for(int i=0;i<n;i++)
	{
		a[i]=1+rand()%100;
	}
}

int main()
{
	
	int s;
	printf("请输入元素的个数n:");
	scanf("%d",&n);
	random();
	printf("\n这n个数依次为: ");
	for(int j=0;j<n;j++)
		printf("%d\t",a[j]);
	s=f(n);
	printf("\n\n这n个数中第二大元素为:%d\n",s);
	return 0;
}

    原文作者:little pepper
    原文地址: https://blog.csdn.net/qq_41045071/article/details/82952130
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。