将大数组拆分为两个数组

6
我有一个由对象组成的大数组,希望将其拆分为两个数组,其中包含交替顺序的对象。
例子: [0, 1, 2, 3, 4, 5, 6] 变成这两个数组(它们应该交替): [0, 2, 4, 6][1, 3, 5] 有很多方法可以拆分数组。但是,如果数组很大,什么方法最有效(成本最低)?

1
你能得到的最好时间复杂度是 O(n)。只需创建两个新数组并循环遍历旧数组,在每次迭代中交替放置元素即可。 - royhowie
7个回答

4
您可以使用“for in stride”循环来按如下方式填充两个结果数组:

extension Array {
    var groupOfTwo:(firstArray:[T],secondArray:[T]) {
        var firstArray:[T] = []
        var secondArray:[T] = []
        for index in stride(from: 0, to: count, by: 2) {
            firstArray.append(self[index])
            if index + 1 < count {
                secondArray.append(self[index+1])
            }
        }
        return (firstArray,secondArray)
    }
}



[0, 1, 2, 3, 4, 5, 6].groupOfTwo.firstArray   // [0, 2, 4, 6]
[0, 1, 2, 3, 4, 5, 6].groupOfTwo.secondArray  // [1, 3, 5]

更新: Xcode 7.1.1 • Swift 2.1
extension Array {
    var groupOfTwo:(firstArray:[Element],secondArray:[Element]) {
        var firstArray:[Element] = []
        var secondArray:[Element] = []
        for index in 0.stride(to: count, by: 2) {
            firstArray.append(self[index])
            if index + 1 < count {
                secondArray.append(self[index+1])
            }
        }
        return (firstArray,secondArray)
    }
}

如果有人在寻找这段代码,它不适用于Swift 2。stride(from: to: by:)不存在,[T]已更改为[Element]。 - earthtrip

4

有多种花式方法可以使用过滤器来完成,但大多数方法可能需要两次遍历而不是一次,因此最好使用for循环。

提前保留空间在这种情况下可能会产生很大的影响,因为如果源数据很大,它将避免新数组增长时进行不必要的重新分配,并且所需空间的计算是基于数组的恒定时间。

// could make this take a more generic random-access collection source
// if needed, or just make it an array extension instead
func splitAlternating<T>(source: [T]) -> ([T],[T]) {
    var evens: [T] = [], odds: [T] = []

    evens.reserveCapacity(source.count / 2 + 1)
    odds.reserveCapacity(source.count / 2)

    for idx in indices(source) {
        if idx % 2 == 0 {
            evens.append(source[idx])
        }
        else {
            odds.append(source[idx])
        }
    }

    return (evens,odds)
}

let a = [0,1,2,3,4,5,6]
splitAlternating(a)  // ([0, 2, 4, 6], [1, 3, 5])

如果性能真的很重要,您可以使用`source.withUnsafeBufferPointer`访问源元素,以避免索引边界检查。
如果数组非常大,并且除了样本少量元素之外,您将不使用生成的数据,则可以考虑使用延迟视图(lazy view)(尽管标准库中的延迟过滤器在这里并没有什么用处,因为它返回序列而不是集合 - 您可能需要编写自己的过滤器)。

提供了许多非常专业的答案。我选择这个答案是因为它更进一步地解释了如何提高性能的方法。 - Onichan

4
更简洁、功能性更强的方法是使用reduce
let a = [0,1,2,3,4,5,6]

let (evens, odds) = a.enumerate().reduce(([Int](),[Int]())) { (cur, next) in
    let even = next.index % 2 == 0
    return (cur.0 + (even ? [next.element] : []),
            cur.1 + (even ? [] : [next.element]))
}

evens // [0,2,4,6]
odds // [1,3,5]

1
大型/巨大的数组在部分处理时常常会出现问题,比如在这种情况下,创建两个额外的数组(即使是半大小)可能既浪费时间又浪费内存。例如,如果您只想计算奇数和偶数位置上数字的平均值和标准差,但这将需要调用一个需要序列作为输入的专用函数,该怎么办呢?
因此,为什么不创建两个子集合,它们不会复制数组内容,而是以透明的方式指向原始数组,以允许查询它们的元素:
extension Collection where Index: Strideable{
    func stride(from: Index, to: Index, by: Index.Stride) -> StridedToCollection<Self> {
        return StridedToCollection(self, from: from, to: to, by: by)
    }
}

struct StridedToCollection<C>: Collection where C: Collection, C.Index: Strideable {
    private let _subscript : (C.Index) -> C.Element
    private let step: C.Index.Stride

    fileprivate init(_ collection: C, from: C.Index, to: C.Index, by: C.Index.Stride)  {
        startIndex = from
        endIndex = Swift.max(to, startIndex)
        step = by
        _subscript = { collection[$0] }
    }

    let startIndex: C.Index
    let endIndex: C.Index

    func index(after i: C.Index) -> C.Index {
        let next = i.advanced(by: step)
        return next >= endIndex ? endIndex : next
    }

    subscript(_ index: C.Index) -> C.Element {
        return _subscript(index)
    }
}
Collection扩展和相关结构将创建一个伪数组,您可以使用它来访问您感兴趣的元素。
使用方法很简单:
let numbers: [Int] = [1, 2, 3, 4]
let stride1 = numbers.stride(from: 0, to: numbers.count, by: 2)
let stride2 = numbers.stride(from: 1, to: numbers.count, by: 2)
print(Array(stride1), Array(stride2))

通过上述方法,您可以迭代两个步长而不必担心会使内存量加倍。如果您确实需要两个子数组,只需使用Array(stride)即可。

0

在我看来,这是最简单的方法

old_list = [0, 1, 2, 3, 4, 5, 6]
new_list1 =[]
new_list2 = []
while len(old_list)>0:
    new_list1.append(old_list.pop(-1))
    if len(old_list) != 0:
        new_list2.append(old_list.pop(-1))

new_list1.reverse()
new_list2.reverse()

0
使用for循环。如果索引值为偶数,则将其发送到一个数组,如果索引值为奇数,则将其发送到另一个数组。

0

我最近需要在一个地方将数组分成两个部分,在另一个地方则需要分成三个部分。于是我写了这段代码:

extension Array {
    /// Splits the receiving array into multiple arrays
    ///
    /// - Parameter subCollectionCount: The number of output arrays the receiver should be divided into
    /// - Returns: An array containing `subCollectionCount` arrays. These arrays will be filled round robin style from the receiving array.
    ///            So if the receiver was `[0, 1, 2, 3, 4, 5, 6]` the output would be `[[0, 3, 6], [1, 4], [2, 5]]`. If the reviever is empty the output
    ///            Will still be `subCollectionCount` arrays, they just all will be empty. This way it's always safe to subscript into the output.
    func split(subCollectionCount: Int) -> [[Element]] {
        precondition(subCollectionCount > 1, "Can't split the array unless you ask for > 1")
        var output: [[Element]] = []

        (0..<subCollectionCount).forEach { (outputIndex) in
            let indexesToKeep = stride(from: outputIndex, to: count, by: subCollectionCount)
            let subCollection = enumerated().filter({ indexesToKeep.contains($0.offset)}).map({ $0.element })
            output.append(subCollection)
        }

        precondition(output.count == subCollectionCount)
        return output
    }
}

它适用于Swift 4.2和5.0(截至Xcode 10.2 beta 2的5.0版本)


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接