LeetCode 1200. 最小绝对差【简单】排序贪心详解 _ O(nlogn)极致优化 + 多版代码 + 证明+易错点

LeetCode 1200. 最小绝对差【简单】排序贪心详解 | O(nlogn)极致优化 多版代码 证明易错点 文章目录一、题目描述【题干约束考点】题目示例题目约束二、解题思路与算法证明2.1 暴力解法超时仅用于理解2.2 核心优化思路本题最优解2.3 算法流程2.4 算法复杂度严格标准三、完整代码实现3.1 暴力超时版原理演示不可提交3.2 最优AC标准版面试/刷题首选3.3 极简Pythonic写法简洁优雅3.4 保姆级注释版零基础易懂3.5 完整可运行测试代码全覆盖用例四、核心细节解析4.1 为什么排序后不需要 abs()4.2 结果为什么天然有序4.3 两次遍历是否可以合并五、易错点总结六、面试考点总结 amp; 刷题模板给定一个元素互不相同的整数数组arr请找出数组中所有满足条件的元素对要求题目核心要求元素对\[a, b\]满足a lt; bb \- a等于全局最小绝对差最终结果按升序字典序返回。题目示例示例 1输入arr [4,2,1,3] 输出[[1,2],[2,3],[3,4]] 解释数组排序后 [1,2,3,4]最小绝对差为 1所有相邻差值为1的数对均为答案。示例 2输入arr [1,3,6,10,15] 输出[[1,3]] 解释最小绝对差为 2仅 1 和 3 满足条件。示例 3输入arr [3,8,-10,23,19,-4,-14,27] 输出[[-14,-10],[19,23],[23,27]]题目约束2 \lt; arr\.length \lt; 10^5\-10^6 \lt; arr\[i\] \lt; 10^6数组内所有元素互不重复数据量级n \lt; 1e5O ( n 2 ) O(n^2)O(n2)暴力枚举必然超时本题唯一可AC的标准解法为排序线性扫描时间复杂度O ( n log ⁡ n ) O(n\log n)O(nlogn)。通过率与难度参考LeetCode 简单题通过率 72.3%属于排序贪心经典模板题面试高频基础算法题。二、解题思路与算法证明2.1 暴力解法超时仅用于理解最直观的思路枚举数组中所有两两元素对计算绝对差先遍历一遍找到全局最小绝对差再二次遍历收集所有符合差值的数对。致命缺陷两两枚举时间复杂度为O ( n 2 ) O(n^2)O(n2)当n10^5时计算量高达10^10完全无法通过测试。2.2 核心优化思路本题最优解关键数学结论核心数学定理解题关键无序数组中最小绝对差一定出现在排序后相邻的两个元素之间非相邻元素不可能产生最小差值。证明严谨推导假设升序数组存在三个元素a \lt; b \lt; c。由单调性可得c \- a \(c \- b\) \ \(b \- a\)必然有c\-a \gt; b\-a且c\-a \gt; c\-b。最终结论任意非相邻元素的差值一定大于相邻差值 → 全局最小绝对差一定只出现在相邻元素。该定理是本题贪心优化的核心理论依据直接将二维枚举问题降维为一维线性扫描是算法优化的关键。2.3 算法流程对原数组进行升序排序一次线性遍历求出排序后数组的最小相邻差值二次线性遍历收集所有相邻差值等于最小差值的数对直接返回结果排序后遍历收集的数对天然有序无需二次排序。2.4 算法复杂度严格标准时间复杂度O ( n log ⁡ n ) O(n\log n)O(nlogn)。算法瓶颈为快速排序两次线性遍历O ( n ) O(n)O(n)不影响整体复杂度。空间复杂度O ( log ⁡ n ) O(\log n)O(logn)。排序递归栈空间未开辟额外数组原地排序。是否可AC是完全通过 1e5 大数据量测试。三、完整代码实现3.1 暴力超时版原理演示不可提交fromtypingimportListclassSolution:defminimumAbsDifference(self,arr:List[int])-List[List[int]]:nlen(arr)min_difffloat(inf)res[]# 第一次遍历找到全局最小绝对差foriinrange(n):forjinrange(i1,n):diffabs(arr[i]-arr[j])ifdiffmin_diff:min_diffdiff# 第二次遍历收集所有符合最小差值的数对foriinrange(n):forjinrange(i1,n):ifabs(arr[i]-arr[j])min_diff:# 保证a ba,barr[i],arr[j]ifab:a,bb,a res.append([a,b])# 按升序排序结果res.sort()returnres3.2 最优AC标准版面试/刷题首选无冗余、速度最快fromtypingimportListclassSolution:defminimumAbsDifference(self,arr:List[int])-List[List[int]]:# 数组升序排序arr.sort()nlen(arr)min_difffloat(inf)# 第一轮遍历寻找最小相邻差值foriinrange(1,n):diffarr[i]-arr[i-1]ifdiffmin_diff:min_diffdiff# 第二轮遍历收集所有最小差值数对ans[]foriinrange(1,n):ifarr[i]-arr[i-1]min_diff:ans.append([arr[i-1],arr[i]])returnans3.3 极简Pythonic写法一行推导、简洁优雅fromtypingimportListclassSolution:defminimumAbsDifference(self,arr:List[int])-List[List[int]]:arr.sort()# 批量计算所有相邻差值取最小值diffs[arr[i]-arr[i-1]foriinrange(1,len(arr))]min_diffmin(diffs)# 列表推导式快速收集结果return[[arr[i-1],arr[i]]foriinrange(1,len(arr))ifarr[i]-arr[i-1]min_diff]3.4 保姆级注释版零基础易懂fromtypingimportListclassSolution:defminimumAbsDifference(self,arr:List[int])-List[List[int]]:# 对数组进行升序排序让最小差值仅出现在相邻元素arr.sort()# 获取数组长度lengthlen(arr)# 初始化最小差值为无穷大min_abs_difffloat(inf)# 第一次遍历遍历所有相邻元素找到最小绝对差foridxinrange(1,length):# 排序后arr[idx] arr[idx-1]无需abscurrent_diffarr[idx]-arr[idx-1]# 更新最小差值ifcurrent_diffmin_abs_diff:min_abs_diffcurrent_diff# 初始化结果列表result[]# 第二次遍历收集所有差值等于最小差值的相邻数对foridxinrange(1,length):ifarr[idx]-arr[idx-1]min_abs_diff:# 数对天然满足左小右大、升序要求result.append([arr[idx-1],arr[idx]])returnresult3.5 完整可运行测试代码全覆盖用例fromtypingimportListclassSolution:defminimumAbsDifference(self,arr:List[int])-List[List[int]]:arr.sort()nlen(arr)min_difffloat(inf)foriinrange(1,n):diffarr[i]-arr[i-1]ifdiffmin_diff:min_diffdiff ans[]foriinrange(1,n):ifarr[i]-arr[i-1]min_diff:ans.append([arr[i-1],arr[i]])returnans# 测试用例if__name____main__:solSolution()print(sol.minimumAbsDifference([4,2,1,3]))# [[1,2],[2,3],[3,4]]print(sol.minimumAbsDifference([1,3,6,10,15]))# [[1,3]]print(sol.minimumAbsDifference([3,8,-10,23,19,-4,-14,27]))# [[-14,-10],[19,23],[23,27]]四、核心细节解析4.1 为什么排序后不需要 abs()**核心原因**数组升序排序后元素满足arr\[i\] \gt; arr\[i\-1\]差值恒为正。省去绝对值运算有效降低常数时间开销优化代码运行效率。4.2 结果为什么天然有序**核心原因**数组整体升序遍历收集的数对从左至右生成天然满足a \lt; b、整体字典升序完全匹配题目输出规范无需二次排序。4.3 两次遍历是否可以合并工程最优解两次遍历。逻辑解耦、代码清晰、便于调试适配刷题、面试、工程开发场景。单次合并遍历优化效果微乎其微且牺牲可读性面试不推荐。五、易错点总结❌ 思维误区1暴力双重循环枚举所有数对 →O(n²)超时大数据必挂❌ 思维误区2无序数组直接计算绝对差 → 无法锁定全局最小差值❌ 代码误区3收集结果后再次排序 → 完全冗余浪费时间✅ 标准正解排序贪心 相邻扫描是本题唯一最优解六、面试考点总结 amp; 刷题模板本题是排序贪心线性扫描的经典入门模板题核心考点不在于代码实现而在于数学思维优化利用数组排序单调性将高复杂度的二维枚举降维为一维遍历复杂度从O ( n 2 ) O(n^2)O(n2)优化至O ( n log ⁡ n ) O(n\log n)O(nlogn)。面试高频提问为什么最小绝对差一定在相邻元素之间需口述数学证明能否使用一次遍历完成解题优缺点是什么暴力解法为什么会超时数据量级瓶颈在哪**通用刷题模板**遇到【数组最小差值、最接近元素、最短间距】类问题统一解题思路先排序 相邻线性扫描快速求解最优解。持续更新LeetCode满分题解包含算法证明、面试考点、多版代码刷题面试两不误点赞收藏不迷路疑问欢迎评论区交流