python list.sort() 与 list.sort(key=itemgetter(0))

Question

我是一个 python 菜鸟，但我正在使用 python 来解决 leetcode 上的问题。我在 leetcode 上解决了一个(合并重叠间隔)。我有以下代码:

    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if len(intervals) < 2: return intervals
        intervals.sort(key=itemgetter(0))
        merged = [intervals[0]]
        for interval in intervals[1:]:
            if merged[-1][1] >= interval[0]: merged[-1][1] = max(merged[-1][1],interval[1])
            else: merged.append(interval)
        return merged

我注意到如果我替换 intervals.sort(key=itemgetter(0))使用 intervals.sort() 我的性能明显变差(分别为 ~80ms 和 ~110ms)

从技术上讲，sort() 与 sort(key=itemgetter(0)) 不是一样的吗？他们不应该有相同的运行时间吗？除非，leetcode 只是与重新编码确切的运行时不一致吗？

Answer 1

您的主要问题已经得到解答。

---

LeetCode 的性能测量根本不准确。您可以在解决问题时忽略他们的基准数据。

class Solution:
    def merge(self, intervals):
        merged = []
        for interval in sorted(intervals, key=lambda x: x[0]):
            if merged and interval[0] <= merged[-1][1]:
                merged[-1][1] = max(merged[-1][1], interval[1])
            else:
                merged.append(interval)
        return merged

class Solution:
    def merge(self, intervals):
        merged = []
        for interval in sorted(intervals):
            if merged and interval[0] <= merged[-1][1]:
                merged[-1][1] = max(merged[-1][1], interval[1])
            else:
                merged.append(interval)
        return merged

---

引用资料

• 有关其他详细信息，您可以查看 Discussion Board .有很多可接受的解决方案，包括各种 languages和解释，高效算法，以及渐近time/space复杂性分析 ^{1 , 2} 在那里。