如何在 Swift 中使用 O(n) 通过参数获取重复项的索引?

Question

我需要通过四舍五入的坐标查找重复项并存储索引，然后通过这些索引从原始数组中删除元素。如何使用 O(n) 执行此操作？

func removeDuplicate(from points: [Point]) -> [Point] {
var originalPoints: [Point] = points
let tempRoundedPoints: [Point] = roundingCoordinates(for: points)
guard tempRoundedPoints.count > 2 else { return originalPoints }
var removableIndexes: [Int] = []
for i in 0..<tempRoundedPoints.count - 2 {
for j in i + 1..<tempRoundedPoints.count - 1 {
if (tempRoundedPoints[i]?.lat == tempRoundedPoints[j]?.lat) && (tempRoundedPoints[i]?.lng == tempRoundedPoints[j]?.lng) {
removableIndexes.append(i)
break
}
}
}
removeWith(indexes: removableIndexes, from: &originalPoints)
return originalPoints
}

Answer 1

这是一个通用函数，用于获取数组中重复项的索引。它要求数组元素符合Equatable和Hashable。它使用Set来存储重复值并返回一个IndexSet。

contains调用Set比调用Array快得多。

extension Collection where Element: Equatable & Hashable, Index == Int {
func indicesOfDuplicates() -> IndexSet {
var index = startIndex
var items = Set<Element>()
var result = IndexSet()
while index < endIndex {
let currentItem = self[index]
if items.contains(currentItem) {
result.insert(index)
} else {
items.insert(currentItem)
}
formIndex(after: &index)
}
return result
}
}

调用数组上的函数

let indexSet = points.indicesOfDuplicates()

要有效地删除数组中索引处的项IndexSet请参阅 removeObjectsAtIndexes for Swift 数组

另一个问题是，由于浮点表示的不精确性，相同的Double值不相等。您可以使用此问题中的此扩展

extension FloatingPoint {
func isNearlyEqual(to value: Self) -> Bool {
return abs(self - value) <= .ulpOfOne
}
}

Answer 2

以下是参考：

var targetPoints = [1, 2, 4, 3, 5, 6]
print("target result: (targetPoints)")
var roundingPoints = [1, 1, 2, 2, 4, 2, 3, 6, 4, 1, 2, 5]
print("what we got: (roundingPoints)")
func sort(arr: [Int]) -> [Int] {
let sortedArr = arr.sorted(by: { $0 < $1 })
return sortedArr
}
roundingPoints = sort(arr: roundingPoints)
print("sorted array: (roundingPoints)")
var index: Int = 0
for i in 0...roundingPoints.count - 1 {
if roundingPoints[index] != roundingPoints[i] {
index += 1
roundingPoints[index] = roundingPoints[i]
}
}
print("result: (roundingPoints[0...index])")

您可以在 .playground 上发帖并尝试一下，希望答案对您有所帮助:)

我认为时间复杂度是 O(n log(n)) + O(n)