如何在Swift的排序数组中正确位置插入元素?

NSArray必须- (NSUInteger)indexOfObject:(id)obj inSortedRange:(NSRange)r

options:(NSBinarySearchingOptions)opts

usingComparator:(NSComparator)cmp确定新对象在排序数组中的插入位置。

在纯Swift中,最好的高性能方法是什么?

类似于以下内容:

var myArray = ["b", "e", "d", "a"]

myArray.sort { $0 < $1 }

// myArray is now [a, b, d, e]

myArray.append("c")

myArray.sort { $0 < $1 }

// myArray is now [a, b, c, d, e]

我想找出正确的位置并插入元素,而不是追加新元素然后对数组进行排序:

let index = [... how to calculate this index ??? ...]

myArray.insert("c", atIndex: index)

回答:

这是在Swift中使用二进制搜索的一种可能的实现方式(来自

http://rosettacode.org/wiki/Binary_search#Swift并进行了一些修改):

extension Array {

func insertionIndexOf(_ elem: Element, isOrderedBefore: (Element, Element) -> Bool) -> Int {

var lo = 0

var hi = self.count - 1

while lo <= hi {

let mid = (lo + hi)/2

if isOrderedBefore(self[mid], elem) {

lo = mid + 1

} else if isOrderedBefore(elem, self[mid]) {

hi = mid - 1

} else {

return mid // found at position mid

}

}

return lo // not found, would be inserted at position lo

}

}

如同indexOfObject:inSortedRange:options:usingComparator:假定数组是相对于比较器排序的。如果该元素已经存在于数组中,则它返回该元素的(任何)索引,或者返回保留该顺序时可以在其中插入的索引。这对应于NSBinarySearchingInsertionIndexNSArray方法的。

用法:

let newElement = "c"

let index = myArray.insertionIndexOf(newElement) { $0 < $1 } // Or: myArray.indexOf(c, <)

myArray.insert(newElement, at: index)

以上是 如何在Swift的排序数组中正确位置插入元素? 的全部内容, 来源链接: utcz.com/qa/427003.html

回到顶部