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:
一样,假设
数组根据比较器排序。
如果该元素已存在于中,则返回该元素的任一(任何)索引
数组,或者可以在保留顺序的情况下插入的索引。这
对应于NSArray
方法的NSBinarySearchingInsertionIndex
。
用法:
let newElement = "c"
let index = myArray.insertionIndexOf(newElement) { $0 < $1 } // Or: myArray.indexOf(c, <)
myArray.insert(newElement, at: index)
关于arrays - 如何在 Swift 中将正确位置的元素插入到排序数组中?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56360259/