基于排序的模式

Source: Dev.to

概述

基于排序的模式通过先对数据进行排序，然后利用排序后的顺序来简化逻辑、降低复杂度，或启用其他高效模式（如双指针或贪心决策）。排序往往能把原本复杂的问题转化为结构化的问题。

何时使用

在以下情况下使用此模式：

• 元素的顺序很重要
• 相对比较是关键
• 需要分组或配对
• 想要使用双指针或贪心逻辑
• 少量的时间增加（排序）能够带来巨大的简化

时间与空间

• 排序时间： O(N log N)
• 后处理： 通常 O(N)
• 空间复杂度： O(1) 或 O(N)，取决于排序实现

核心思路

• 先对数组进行排序
• 利用排序属性来：
  • 消除不必要的比较
  • 做出单调决策
  • 易于发现模式
  • 排序后进行线性扫描或指针技术

示例 1：使用排序的 Two Sum

问题： 判断是否存在一对数的和等于目标值。

逻辑：

1. 对数组进行排序。
2. 使用左右两端的指针。

def two_sum_sort(nums, target):
    nums.sort()
    left = 0
    right = len(nums) - 1

    while left  0 and nums[i] == nums[i - 1]:
            continue

        left = i + 1
        right = len(nums) - 1

        while left  2:
                return False

    return True

识别清单

思考以下问题：

• 排序后是否简化了决策？
• 排序是否能够解锁线性扫描？
• 相对顺序是否重要？
• N log N 的时间复杂度是否可接受？

如果答案是肯定的，则适用基于排序的模式。

常见陷阱

• 排序后忘记处理重复元素。
• 假设需要稳定排序却并非必要。
• 在必须保留原始顺序时进行排序。
• 忽视更快的非排序解法。

总结

• 先排序，再思考。
• 为双指针和贪心策略提供可能。
• 常常是降低复杂度的关键。
• 必须掌握的基础问题求解模式。