Question 68124 in IOS Swift Question posted in
The official documentation can be found here.

How to get indexes of duplicates by parameters with O(n) in Swift? – Ios swift

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
}
Tags:

2

Answers


  1. 0

    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.

    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
    }
}

    Call the function on the array

    let indexSet = points.indicesOfDuplicates()

    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
    }
}
    Login or Signup to reply.
  2. 0

    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)

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search