arrays - 在 Swift 中将排序数组拆分为子数组的自定义操作

Question

我想在一个sorted Array(或Collection 或Sequence，等等)上编写自定义操作执行以下操作:

从头开始，它会查看每对相邻的元素。如果两者满足条件，则继续下一对，否则将其拆分。所以最后，我会有一个数组数组，其中条件在同一子数组内的元素之间得到满足，但在不同子数组之间则不满足。以下是否正确有效？

extension Array {
    public func splitSorted(by condition: (Element, Element)->(Bool)) -> [[Element]] {
        var result = [[Element]]()
        var start = 0
        var end = 0

        while end != self.count - 1 {
            while end < self.count && condition(self[start], self[end]) {
                end += 1
            }
            result.append(Array(self[start..<end]))
            start = end
        }

        return result
    }
}

Answer 1

您的代码无法正常工作，因为:

• 您不比较相邻 元素。
• 首先将第一个元素与其自身进行比较，这会导致一个永无止境的循环。
• 未正确处理空数组。

这是您的方法的一种工作变体:

extension Array {
    public func splitSorted(by condition: (Element, Element)->(Bool)) -> [[Element]] {
        var result = [[Element]]()
        var start = startIndex
        while start != endIndex {
            var end = start
            repeat {
                end += 1
            } while end != endIndex && condition(self[end - 1], self[end])
            result.append(Array(self[start..<end]))
            start = end
        }
        return result
    }
}

例子:

let arr = [1, 2, 3, 2, 3, 4, 3, 4, 5]
let split = arr.splitSorted(by: <)
print(split) // [[1, 2, 3], [2, 3, 4], [3, 4, 5]]

Sequence 的概括是:

extension Sequence {
    public func splitSorted(by condition: (Element, Element)->(Bool)) -> [[Element]] {
        var it = makeIterator()
        guard var currentElem = it.next() else {
            return [] // Input sequence is empty
        }
        var result = [[Element]]()
        var currentSegment = [currentElem]
        while let nextElem = it.next() {
            if condition(currentElem, nextElem) {
                // Append to current segment:
                currentSegment.append(nextElem)
            } else {
                // Start new segment:
                result.append(currentSegment)
                currentSegment = [nextElem]
            }
            currentElem = nextElem
        }
        result.append(currentSegment)
        return result
    }
}

示例(按相同的奇偶性对斐波那契数列进行分组):

// From https://stackoverflow.com/a/40203183/1187415
let fibs = sequence(state: (0, 1),
                    next: { (pair: inout (Int, Int)) -> Int? in
                        defer { pair = (pair.1, pair.0 + pair.1) }
                        return pair.1
                    })

print(fibs.prefix(12).splitSorted(by: { ($0 - $1) % 2 == 0 }))
// [[1, 1], [2], [3, 5], [8], [13, 21], [34], [55, 89], [144]]