LeetCode「Minimum Absolute Difference」代码提交超时问题求助

你的代码在本地小数据量下正常，但提交超时的核心问题是频繁调用arr.index(i)——这个方法会从头遍历数组查找元素的索引，每次调用时间复杂度是O(n)，再加上外层两次O(n)的循环，整体时间复杂度飙升到O(n²)，面对大规模数组时必然超时。

优化思路 #

数组排序后，最小绝对差一定出现在相邻元素之间（非相邻元素的差肯定大于等于相邻元素的差），因此我们只需要遍历相邻元素即可，无需对所有元素对做检查。

优化后的代码 #

class Solution(object):
    def minimumAbsDifference(self, arr):
        arr.sort()
        min_diff = float('inf')
        result = []
        
        # 第一次遍历，找出最小绝对差
        for i in range(1, len(arr)):
            diff = arr[i] - arr[i-1]  # 排序后后项减前项无需abs，结果非负
            if diff < min_diff:
                min_diff = diff
        
        # 第二次遍历，收集所有符合最小差的元素对
        for i in range(1, len(arr)):
            if arr[i] - arr[i-1] == min_diff:
                result.append([arr[i-1], arr[i]])
        
        return result

优化点说明 #

• 用索引遍历替代元素遍历，彻底避免arr.index(i)的O(n)开销，两次遍历均为O(n)，加上排序的O(n log n)，整体时间复杂度为O(n log n)，完全符合题目性能要求。
• 排序后相邻元素的差为非负数，省去abs()计算，小幅提升效率。
• 用float('inf')初始化最小差值，比固定值1000更通用，适配所有可能的数组元素范围。

内容的提问来源于stack exchange，提问作者some random dude