【题目来源】学而思编程零距离【题目描述】小猴最近刚刚在数学课上学完负数老师给小猴布置了一个任务有n nn个整数a 1 , a 2 , … , a n a_1,a_2,\dots,a_na1​,a2​,…,an​要求找出其中最接近0 00的数字。如果有多种可能只需要给出其中最大的数字。【输入】第一行一个整数n nn第二行n个整数a 1 , a 2 , … , a n a_1,a_2,\dots,a_na1​,a2​,…,an​。【输出】一行一个整数表示最接近0的数字。【输入样例】5 -4 -2 1 4 8【输出样例】1【核心思想】问题分析给定n nn个整数找出最接近0 00的数字。若绝对值相同取较大的那个。这是一个线性扫描 绝对值比较问题关键在于同时维护绝对值最小和数值最大的两个条件。算法选择单变量维护用minn同时记录当前最优解比较时先比绝对值绝对值相同时比原值贪心更新遍历每个数若更优则替换关键步骤初始化读取n nnminn \infty极大值线性扫描遍历i ii从1 11到n nn读取a aa若∣ a ∣ ∣ m i n n ∣ |a| |minn|∣a∣∣minn∣minn a绝对值更小更新否则若∣ a ∣ ∣ m i n n ∣ |a| |minn|∣a∣∣minn∣且a m i n n a minnaminnminn a绝对值相同取较大值输出minn时间/空间复杂度时间复杂度O ( n ) O(n)O(n)线性扫描空间复杂度O ( 1 ) O(1)O(1)仅需一个变量贪心扫描的核心思想双重比较条件第一关键字为绝对值越小越优第二关键字为原值越大越优天然对应最接近0 00且最大的要求单变量状态压缩无需存储所有数当前最优解minn已包含足够信息新数只需与之比较流式处理支持在线输入无需预存全部数据绝对值函数abs()统一处理正负数避免分支判断适用于单目标极值 平局打破类问题线性扫描配合双重比较即可解决【算法标签】#模拟【代码详解】#includebits/stdc.husingnamespacestd;intmain(){intn;cinn;// 输入数字个数intminn1e9;// 初始化最小值使用较大的数for(inti1;in;i)// 遍历n个数{inta;cina;// 输入当前数// 如果绝对值更小更新minnif(abs(a)abs(minn)){minna;}// 如果绝对值相等取较大的数if(abs(a)abs(minn)){minnmax(minn,a);}}coutminn;// 输出结果return0;}【运行结果】5 -4 -2 1 4 8 1