Swift中如何以O(n)时间复杂度按参数获取重复项索引并去重

核心逻辑是用哈希表替代双层循环做重复判断，哈希表的插入、查询操作平均时间复杂度为O(1)，配合单次遍历就能把整体复杂度压到线性级别。

实现思路 #

• 先批量计算所有坐标点四舍五入后的结果，和原数组索引一一对应
• 初始化一个哈希集合，用来记录已经出现过的唯一四舍五入坐标标识
• 单次遍历所有四舍五入后的坐标：如果当前坐标标识已经在集合里，说明是重复项，把对应索引加入待删除列表；如果不在集合里，就把标识存入集合，保留当前点
• 最后把待删除索引对应的元素从原数组中移除即可

原有代码问题修正 #

你之前的实现除了复杂度不达标，还有两个隐藏bug：

1. 循环范围写的是0..<tempRoundedPoints.count - 2和i+1..<tempRoundedPoints.count - 1，会漏掉数组最后两个元素的去重判断
2. 待删除索引如果不做从大到小排序就直接删除，会因为前面元素被移除导致后面的索引偏移，出现删错元素的问题

优化后代码 #

func removeDuplicate(from points: [Point]) -> [Point] {
    // 元素数小于2时不存在重复，直接返回
    guard points.count >= 2 else { return points }
    let tempRoundedPoints = roundingCoordinates(for: points)
    // 存储已经出现过的四舍五入坐标键
    var seenPointKeys = Set<String>()
    var removableIndexes = [Int]()
    
    for (index, roundedPoint) in tempRoundedPoints.enumerated() {
        // 空坐标默认保留，有特殊需求可以自行调整逻辑
        guard let lat = roundedPoint?.lat, let lng = roundedPoint?.lng else {
            continue
        }
        // 用经纬度拼接字符串作为哈希键，无需修改原有Point结构
        let uniqueKey = "\(lat),\(lng)"
        if seenPointKeys.contains(uniqueKey) {
            removableIndexes.append(index)
        } else {
            seenPointKeys.insert(uniqueKey)
        }
    }
    
    var result = points
    removeWith(indexes: removableIndexes, from: &result)
    return result
}

性能说明 #

• 时间复杂度：全流程仅做线性遍历，哈希集合操作均为O(1)平均复杂度，整体稳定在O(n)，相比原有O(n²)的双层循环在大数据量下性能提升非常明显
• 空间复杂度：最坏情况（无任何重复点）下哈希集合需要存储n个坐标键，空间复杂度O(n)，属于常规的空间换时间实现

提示：请确保你使用的removeWith(indexes:from:)方法内部会先把传入的索引按从大到小排序再执行删除操作，避免索引错位问题。

内容的提问来源于stack exchange，提问作者Hlony