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

Question

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
}

If the order isn't important, you might be able to use `Dictionary.grouping(_:by:)`, where key would rounded value. if it's important, you could use an `OrderedDictionary`, populating it by iteration, where key would be the rounded location, and value the real location if order is important. — Larme, Jun 17 '22 at 09:15
@Larme Сan you give an example in the answer, because I tried through the dictionary and I got porridge. I think I missed something. — Hlony, Jun 17 '22 at 09:17
If the order isn't important and it isn't mandatory to call `removeWith` then I would create the array of rounded values, create a `Set` from that array and then convert the set back to an array. `==` needs to be defined correctly on `Point` — Paulw11, Jun 17 '22 at 09:42
@Paulw11 The set will remove duplicates from the array with rounded coordinates, but I need to get the indices and remove them from the original array. Perhaps I did not understand your idea, then it would be cool to see an example. — Hlony, Jun 17 '22 at 09:46

vadian · Answer 1 · 2022-06-17T14:59:28.487

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

Given solution in my case returns 0 indexes. I did hash by lng, lat and comparable by id. What could be the problem? I need specifically to compare lng, lat. — Hlony, Jun 17 '22 at 10:23
Yes. Your `==` function should be something like `return lhs.lat == hrs.lat && lhs.lng = rhs.lng }` — Paulw11, Jun 17 '22 at 10:35

Bomi Chen · Answer 2 · 2022-06-17T11:09:41.473

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)

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

2 Answers2