How to get indexes of duplicates by parameters with O(n) in Swift?-CodePudding

I need to find duplicates by rounded coordinates and store the indices, then remove elements from the original array by these indices. How can I do this with 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
}

CodePudding user response：

This is a generic function to get the indices of duplicates in an array. It requires that the array element conforms to Equatable and Hashable. It uses a Set to store the duplicate values and returns an IndexSet.

contains called on a Set is much faster than called on an Array.

func indicesOfDuplicates<T: Equatable & Hashable>(in array: [T]) -> IndexSet {
    var index = array.startIndex
    var duplicates = Set<T>()
    var result = IndexSet()
    while index < array.endIndex {
        let currentItem = array[index]
        if duplicates.contains(currentItem) {
            result.insert(index)
        } else {
            duplicates.insert(currentItem)
        }
        array.formIndex(after: &index)
    }
    return result
}

To remove the items in an array at indexes in an IndexSet efficiently see removeObjectsAtIndexes for Swift arrays

Another problem is that identical Double values are not equal due to the imprecise nature of floating point representation. You could use this extension found in this question

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

CodePudding user response：

Here's for reference:

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])")

ps. you can post in .playground and try it, hope the answer will help :)

I think the time complexity is O(n log(n)) O(n)