
寻找一个数组中的最大和最小数
工作一段快两年了,感觉之前学的数据结构和算法基本忘得差不多了,最近一段时间准备复习一下相关知识。
有一个求数组中最大和最小数的题目,基本的思路是遍历一遍数组,然后每个一个元素都和最大值和最小值比较,时间复杂度是2(N-1)或2N。
比较简单的一种减少复杂度的方法是把数组的元素两两分组比较,然后较大的数和max比较,较小的数和min比较,这种实现方法的时间复杂度是1.5N。
还有一种是采用分治法,比较次数也是1.5N,思路是将数组一分为二,分别获取两个子数组的最大和最小值,然后进行取两个子数组中较小的最小值和较大的最大值。
O(N) = (N/2 + N/4 + … + N/2^(log2(N))) = 3N/2 ?
#include <cstdio>
void max_min(int a[], int begin, int end, int *max, int *min) {
if (end == begin) {
*max = a[begin];
*min = a[end];
return;
}
int l_max, r_max;
int l_min, r_min;
max_min(a, begin, begin + (end - begin) / 2, &l_max, &l_min);
max_min(a, begin + (end - begin) / 2 + 1, end, &r_max, &r_min);
*max = l_max > r_max ? l_max : r_max;
*min = l_min < r_min ? l_min : r_min;
}
int main() {
int array[] = {5,7,8,9,11,13,45,8,9,23,45,97,3,2,7,14,64};
int len = sizeof(array) / sizeof(int);
int max = array[0];
int min = array[0];
for (int i = 1; i < len; ++i) {
if (array[i] > max) {
max = array[i];
} else if (array[i] < min){
min = array[i];
}
}
printf("max:%d min:%d\", max, min);
int start = -1;
if (len & 0x1) {
start = 1;
} else {
start = 0;
}
for (int i = start; i < len; i+=2) {
if (array[i] > array[i + 1]) {
if (array[i] > max) max = array[i];
if (array[i + 1] < min) min = array[i + 1];
} else if (array[i] < array[i + 1]) {
if (array[i] < min) min = array[i];
if (array[i + 1] > max) max = array[i + 1];
}
}
printf("max:%d min:%d\", max, min);
max_min(array, 0, len - 1, &max, &min);
printf("max:%d min:%d\", max, min);
return 0;
}
数据分析咨询请扫描二维码
若不方便扫码,搜微信号:CDAshujufenxi
解析 response.text 与 response.content 的核心区别 在网络数据请求与处理的场景中,开发者经常需要从服务器返回的响应中提取数 ...
2025-07-22解析神经网络中 Softmax 函数的核心作用 在神经网络的发展历程中,激活函数扮演着至关重要的角色,它们为网络赋予了非线性能力, ...
2025-07-22CDA数据分析师证书考取全攻略 一、了解 CDA 数据分析师认证 CDA 数据分析师认证是一套科学化、专业化、国际化的人才考核标准, ...
2025-07-22左偏态分布转正态分布:方法、原理与实践 左偏态分布转正态分布:方法、原理与实践 在统计分析、数据建模和科学研究中,正态分 ...
2025-07-22你是不是也经常刷到别人涨粉百万、带货千万,心里痒痒的,想着“我也试试”,结果三个月过去,粉丝不到1000,播放量惨不忍睹? ...
2025-07-21我是陈辉,一个创业十多年的企业主,前半段人生和“文字”紧紧绑在一起。从广告公司文案到品牌策划,再到自己开策划机构,我靠 ...
2025-07-21CDA 数据分析师的职业生涯规划:从入门到卓越的成长之路 在数字经济蓬勃发展的当下,数据已成为企业核心竞争力的重要来源,而 CD ...
2025-07-21MySQL执行计划中rows的计算逻辑:从原理到实践 MySQL 执行计划中 rows 的计算逻辑:从原理到实践 在 MySQL 数据库的查询优化中 ...
2025-07-21在AI渗透率超85%的2025年,企业生存之战就是数据之战,CDA认证已成为决定企业存续的生死线!据麦肯锡全球研究院数据显示,AI驱 ...
2025-07-2035岁焦虑像一把高悬的利刃,裁员潮、晋升无望、技能过时……当职场中年危机与数字化浪潮正面交锋,你是否发现: 简历投了10 ...
2025-07-20CDA 数据分析师报考条件详解与准备指南 在数据驱动决策的时代浪潮下,CDA 数据分析师认证愈发受到瞩目,成为众多有志投身数 ...
2025-07-18刚入职场或是在职场正面临岗位替代、技能更新、人机协作等焦虑的打工人,想要找到一条破解职场焦虑和升职瓶颈的系统化学习提升 ...
2025-07-182025被称为“AI元年”,而AI,与数据密不可分。网易公司创始人丁磊在《AI思维:从数据中创造价值的炼金术 ...
2025-07-18CDA 数据分析师:数据时代的价值挖掘者 在大数据席卷全球的今天,数据已成为企业核心竞争力的重要组成部分。从海量数据中提取有 ...
2025-07-18SPSS 赋值后数据不显示?原因排查与解决指南 在 SPSS( Statistical Package for the Social Sciences)数据分析过程中,变量 ...
2025-07-18在 DBeaver 中利用 MySQL 实现表数据同步操作指南 在数据库管理工作中,将一张表的数据同步到另一张表是常见需求,这有助于 ...
2025-07-18数据分析师的技能图谱:从数据到价值的桥梁 在数据驱动决策的时代,数据分析师如同 “数据翻译官”,将冰冷的数字转化为清晰的 ...
2025-07-17Pandas 写入指定行数据:数据精细化管理的核心技能 在数据处理的日常工作中,我们常常需要面对这样的场景:在庞大的数据集里精 ...
2025-07-17解码 CDA:数据时代的通行证 在数字化浪潮席卷全球的今天,当企业决策者盯着屏幕上跳动的数据曲线寻找增长密码,当科研人员在 ...
2025-07-17CDA 精益业务数据分析:数据驱动业务增长的实战方法论 在企业数字化转型的浪潮中,“数据分析” 已从 “加分项” 成为 “必修课 ...
2025-07-16