精选文章 分治法求最大和次大元素

分治法求最大和次大元素

作者:成龙大侠 时间: 2019-11-07 09:54:57
成龙大侠 2019-11-07 09:54:57

传统求一组数据内次最大和次大元素有顺序搜索法(时间复杂度O(n)),排序法(O(n*logn))等。而分治法可以把时间复杂度降低到O(logn)级别,但是相对来说实现起来也复杂一点

code:

#include 
#include 

using namespace std;
const int INF = 0x3f3f3f3f;

void solve(int a[], int left, int right, int &max1, int &max2)
{
	if(left == right)	// 递归出口,区间内只有一个元素 
	{
		max1 = a[left];
		max2 = -INF;
	}
	else if(left + 1 == right)	// 递归出口,区间内有两个元素 
	{
		max1 = max(a[left], a[right]);
		max2 = min(a[right], a[right]);
	}
	else
	{
		int mid = (left + right) / 2;
		int lmax1, lmax2;
		int rmax1, rmax2;
		solve(a, left, mid, lmax1, lmax2); 	// 递归寻找左边 
		solve(a, mid+1, right, rmax1, rmax2);	// 递归寻找右边 
		if(lmax1 > rmax1)
		{
			max1 = lmax1;
			max2 = max(lmax2, rmax1);
		}
		else
		{
			max1 = rmax1;
			max2 = max(lmax1, rmax2);
		}
	}
}

int main()
{
	int n;
	int a[1000];
	cin >> n;
	for(int i = 0; i < n; i++)
		cin >> a[i];
	int max1, max2;
	solve(a, 0, n-1, max1, max2);
	cout << max1 << " " << max2 << endl;
	
	
	
	return 0;
 } 

 

勿删,copyright占位
分享文章到微博
分享文章到朋友圈

上一篇:静态内部类和非静态内部类的区别

下一篇:[CDH 基础]-- tsquery 语言指南(CDH 6.3.0)

您可能感兴趣

  • 2020B证(安全员)考试及B证(安全员)模拟考试题库

    题库来源:安全生产模拟考试一点通公众号小程序 2020B证(安全员)考试及B证(安全员)模拟考试题库,包含B证(安全员)考试答案解析及B证(安全员)模拟考试题库练习。由安全生产模拟考试一点通公众号结合国家B证(安全员)考试最新大纲及B证(安全员)考试真题出具,有助于B证(安全员)考试软件考前练习。 1、【单选题】多台挖掘机在同一作用面机械开挖,挖掘机间距应大于( )。( B ) A、5m B...

  • OpenCV 识别图片中的米粒个数,并计算米粒的平均面积和长度(转)

    介绍 OpenCV+Python 使用OpenCV构建图像识别算法,识别图片中的米粒个数,并计算米粒的平均面积和长度 软件架构 模块:OpenCV 4.0.0.21 编程语言:Python 3.7.2 编译器:PyCharm 2018 程序设计思路 首先介绍一下程序设计的思路: 图像采集(取到图像):可以用摄像头拍摄或者图片直接导入 图像预处理:对图像进行灰度化 基于灰度的阈值分割:使用局部...

  • 多线程基础例题

    通常使用锁方法(Synchronized修饰方法)、锁代码块(Synchronized块)、信号量(Semaphore)、Lock锁 1、要求线程a执行完才开始线程b, 线程b执行完才开始主线程 思路:由题意可知会有两条副线程a和b,编写好a,b的内容后,在主线程中启动两个线程。 关键点在于,一旦开启线程,线程的执行完全是由各自抢占cpu的能力而定,是人为不可控的,为了实现题目中的要求,我们...

  • JetPack WorkManager

    1.概览 官方文档:WorkManager 谷歌实验室:官方教程 官方案例:android-workmanager WorkManger介绍视频:中文官方介绍视频 谷歌工程师博客:https://medium.com/androiddevelopers/workmanager-basics-beba51e94048 Android JetPack实例学习:https://www.jiansh...

  • IntellIJ IDEA2020新功能

    一、java 1、Java 14支持:记录和模式匹配 IntelliJ IDEA 2020.1添加了对Java 14及其新功能的支持。IDE不仅添加了对Records的完整代码洞察支持,而且还使您能够快速创建新记录并生成其构造函数和组件,并警告存在的错误。您还将发现对instanceof运算符的模式匹配的支持,包括新的检查和快速修复,该快速修复通过用新的简洁模式变量替换它们来快速简化冗长的i...

  • CRM管理策略为什么能增加企业利润?

    CRM(客户关系管理)是一种管理策略,它的核心在于企业用来管理它们与现有客户和潜在客户之间互动的所有活动、策略与技术,让你的客户在不同阶段的客户生命周期都有最佳体验。在很多企业内,我们都能听到“顾客至上”这句话,如果制定有效的CRM管理策略,带给客户良好的体验,可以帮助企业实现利润的增长。 为什么CRM管理策略能增加企业利润? 无论在哪个行业,客户忠诚度都是非常重要,CRM帮助企业与客户建立...

  • Java异常面试题(2020最新版)

    文章目录 Java异常架构与异常关键字 Java异常简介 Java异常架构 1. Throwable 2. Error(错误) 3. Exception(异常) 运行时异常 编译时异常 4. 受检异常与非受检异常 受检异常 非受检异常 Java异常关键字 Java异常处理 声明异常 抛出异常 捕获异常 如何选择异常类型 常见异常处理方式 直接抛出异常 封装异常再抛出 捕获异常 自定义异常 t...

  • 中国第五个直辖市,我来说两句

    中国第五个直辖市,我来说两句 最近网上有很多网民在讨论新的直辖市的问题,很多人鼓吹说深圳很有可能成为第五个直辖市,有人说武汉应该成为直辖市。去年回河南长葛岳父家探亲,发现本地人在说郑州可能成为直辖市。实际上,谁是最新的直辖市,是一个老生常谈的问题。不仅仅大城市,很多二三线城市的市民,都在网上表达希望自己所在的城市成为新的直辖市的愿望和幻想。 众所周知,想成为一个直辖市是有设立条件的。首先它要...

华为云40多款云服务产品0元试用活动

免费套餐,马上领取!
CSDN

CSDN

中国开发者社区CSDN (Chinese Software Developer Network) 创立于1999年,致力为中国开发者提供知识传播、在线学习、职业发展等全生命周期服务。