Swift中已排序数组自定义拆分操作的正确性与效率问询

嘿，我来帮你拆解这个数组自定义操作的实现问题～

首先明确你的核心需求：给数组（你提到是已排序的，不过这个逻辑也适用于非排序数组）添加一个自定义操作，遍历相邻元素，满足指定条件就留在同一个子数组，不满足则拆分，最终返回子数组的集合。

先假设你的扩展代码类似这样（常见的正确实现）： #

extension Array {
    public func splitByAdjacentCondition(_ condition: (Element, Element) -> Bool) -> [[Element]] {
        guard !isEmpty else { return [] }
        
        var result: [[Element]] = []
        var currentSubarray = [first!]
        
        for element in dropFirst() {
            if condition(currentSubarray.last!, element) {
                currentSubarray.append(element)
            } else {
                result.append(currentSubarray)
                currentSubarray = [element]
            }
        }
        // 别忘了把最后一组子数组加入结果
        result.append(currentSubarray)
        return result
    }
}

正确性分析 #

这个实现是完全正确的，原因如下：

• 处理了空数组的边界情况，直接返回空数组，避免后续越界；
• 处理了单元素数组，返回包含该元素的单元素子数组；
• 遍历逻辑清晰：从第二个元素开始，逐个检查和当前子数组最后一个元素是否满足条件，满足则追加，不满足则归档当前子数组并重置；
• 不会遗漏最后一组子数组（这是很多人容易犯的错误）。

另外，虽然你提到是“已排序数组”，但这个实现并不依赖数组的排序状态——只要你的条件是针对相邻元素的判断，不管数组是否有序，都能正确拆分。

效率分析 #

这个实现的效率已经是最优级了：

• 时间复杂度：O(n)，只需要遍历原数组一次，每个元素仅被处理一次，没有嵌套循环或重复计算；
• 空间复杂度：O(n)，这是无法避免的——因为最终要返回所有原元素组成的子数组，总元素数和原数组一致。如果想进一步优化，可以给result预先调用reserveCapacity（比如预估子数组数量），但在无法确定子数组数量的场景下，这个优化的收益有限，原代码的效率已经足够高。

小提示 #

如果你的条件是针对排序数组的特定场景（比如相邻元素差值不超过某个值、连续递增等），可以基于这个扩展封装更具体的方法，但核心逻辑不需要改动。

内容的提问来源于stack exchange，提问作者Jack Guo