秒懂算法 | 选第二大元素的分治算法

简介: 运用“分而治之”的思想,解决选第二大元素问题。

640.jpg


给定n个元素,找出元素中的第二大元素。该问题如果用线性扫描的方法,首先找出最大值,比较n-1次;然后从n-1个元素中找出最大值即为n个元素的第二大元素,线性扫描比较n-2次,所以找到n个元素的第二大元素需要比较2n-3次。下面考虑设计一个选第二大元素的分治算法。

01、问题分析——分与治的方法

(1) 分解:将n个元素从中间一分为二,当n为奇数时,两个子问题的规模大致相等;当n为偶数时,两个子问题的规模完全相等,均为n/2。

(2) 治理:递归两个子问题,分别求出两个子问题的最大值,同时将被淘汰的较小元素记录在较大元素的列表中。比较子问题的最大值,取较大元素为原问题的最大值。最后在最大值淘汰的元素列表中找出最大值即为原问题的第二大元素。

如找10个元素6,12,3,7,2,18,90,87,54,23的第二大元素。

首先从中间一分为二,递归找出左半部分的最大值,递归找出右半部分的最大值,同时将被淘汰的较小元素记录在淘汰它的元素列表中,如图1所示。

640.png


■ 图1 分解及淘汰元素列表示意

比较左半部分的最大值和右半部分的最大值,取较大者作为整个问题的最大值,即90。最后在最大值90的淘汰元素列表中找最大值,即87,即为整个问题的第二大元素。

02、算法设计

1●设计思想

通过问题分析,n个元素存储在列表a_list中,令left表示子问题的下边界,right表示子问题的上边界,则a_list[left:right]表示不同的子问题。其分解步骤表示为mid = (left+right)/2;递归的边界条件表示为left≥right,当问题规模为1时,单个元素本身就是序列的最大值。

治理划分为两个阶段:
①递归求解a_list[left:mid]和a_list[mid+1:right]两个子问题的最大值left_max和right_max,同时将被淘汰的元素放入淘汰它的元素对应的列表中。比较left_max和right_max,取较大的作为n个元素的最大值。
②在n个元素的最大值淘汰的元素列表中,顺序查找最大值,即为第二大元素。

2●伪码描述

第一个阶段找n个元素的最大值,伪码描述如下:

640.png

目录
相关文章
|
1月前
|
人工智能 自然语言处理 算法
当prompt策略遇上分治算法,南加大、微软让大模型炼成“火眼金睛”
【2月更文挑战第24天】当prompt策略遇上分治算法,南加大、微软让大模型炼成“火眼金睛”
31 2
当prompt策略遇上分治算法,南加大、微软让大模型炼成“火眼金睛”
|
1月前
|
算法 Java
[Java·算法·简单] LeetCode 27. 移除元素 详细解读
[Java·算法·简单] LeetCode 27. 移除元素 详细解读
31 1
|
1月前
|
存储 缓存 算法
【数据结构与算法】【小白也能学的数据结构与算法】递归 分治 迭代 动态规划 无从下手?一文通!!!
【数据结构与算法】【小白也能学的数据结构与算法】递归 分治 迭代 动态规划 无从下手?一文通!!!
|
19天前
|
算法
数据结构和算法学习记录——习题-移除链表元素
数据结构和算法学习记录——习题-移除链表元素
13 0
|
4天前
|
存储 算法 Java
Java查找算法概览:二分查找适用于有序数组,通过比较中间元素缩小搜索范围;哈希查找利用哈希函数快速定位,示例中使用HashMap存储键值对,支持多值关联。
【6月更文挑战第21天】Java查找算法概览:二分查找适用于有序数组,通过比较中间元素缩小搜索范围;哈希查找利用哈希函数快速定位,示例中使用HashMap存储键值对,支持多值关联。简单哈希表实现未涵盖冲突解决和删除操作。
13 1
|
12天前
|
算法
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
|
16天前
|
存储 算法 数据挖掘
python5种算法模拟螺旋、分层填充、递归、迭代、分治实现螺旋矩阵ll【力扣题59】
python5种算法模拟螺旋、分层填充、递归、迭代、分治实现螺旋矩阵ll【力扣题59】
|
20天前
|
算法 搜索推荐 Java
【经典算法】LeetCode 215. 数组中的第K个最大元素(Java/C/Python3实现含注释说明,Medium)
【经典算法】LeetCode 215. 数组中的第K个最大元素(Java/C/Python3实现含注释说明,Medium)
10 3
|
5天前
|
算法
数据结构与算法===分治算法
数据结构与算法===分治算法
|
12天前
|
算法 C++
计算机算法设计与分析 第2章 递归与分治策略 (笔记)
计算机算法设计与分析 第2章 递归与分治策略 (笔记)