如何移除数组中的重复坐标及两个重复坐标之间的所有坐标

核心逻辑 #

针对迷宫路径中包含回溯尝试坐标的问题，采用栈结构配合重复坐标检测实现剪枝，自动删除两个重复坐标之间的所有无效绕路片段：

• 遍历原始路径的所有坐标，用栈存储当前有效路径
• 若当前坐标未在栈中出现，直接压入栈
• 若当前坐标已在栈中出现，将栈截断到该重复坐标的位置，自动清除中间所有无效路径

代码实现 #

基础版（易理解，适合短路径场景） #

def prune_maze_path(raw_path):
    stack = []
    for coord in raw_path:
        coord_tuple = tuple(coord)
        # 检查当前坐标是否已存在于有效路径中
        exist_coords = [tuple(c) for c in stack]
        if coord_tuple in exist_coords:
            # 截断到重复坐标的位置
            idx = exist_coords.index(coord_tuple)
            stack = stack[:idx + 1]
        else:
            stack.append(coord)
    return stack

# 测试示例
raw_array = [[3,3], [2,3], [1,3], [2,3], [3,3], [3,4], [3,5]]
final_array = prune_maze_path(raw_array)
print(final_array)
# 输出结果：[[3, 3], [3, 4], [3, 5]]

优化版（高效，适合长路径场景） #

通过额外维护哈希表存储坐标和索引的映射，避免每次遍历栈查询坐标位置，时间复杂度优化为O(n)：

def prune_maze_path_optimized(raw_path):
    stack = []
    coord_index_map = {}
    for coord in raw_path:
        coord_tuple = tuple(coord)
        if coord_tuple in coord_index_map:
            truncate_idx = coord_index_map[coord_tuple]
            # 清除哈希表中被截断部分的记录
            for c in stack[truncate_idx + 1:]:
                del coord_index_map[tuple(c)]
            stack = stack[:truncate_idx + 1]
        else:
            stack.append(coord)
            coord_index_map[coord_tuple] = len(stack) - 1
    return stack

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