求数组元素到最近0值的步数算法实现求助

嘿，我来帮你搞定这个问题！你的初始思路其实找对方向了——先定位所有0的位置，再处理它们之间的间隙，但目前的代码只从后一个0往回倒计步数，完全没考虑到每个位置到前一个0的距离，所以才会出错。咱们一步步来完善它～

方法一：两次遍历法（高效简洁） #

这个方法的核心是分别从左到右、从右到左遍历数组，记录每个位置到左侧最近0的距离和右侧最近0的距离，最后取两者的最小值。时间复杂度是O(n)，空间复杂度O(n)（用来存结果），非常高效。

代码实现 #

def space_to_empty_lots(arr: list) -> list:
    n = len(arr)
    # 初始化结果数组，用无穷大表示初始状态下没有找到0
    result = [float('inf')] * n
    
    # 第一次遍历：从左到右，记录每个位置到左侧最近0的距离
    for i in range(n):
        if arr[i] == 0:
            # 当前位置是0，距离为0
            result[i] = 0
        elif i > 0:
            # 继承前一个位置的距离+1（因为前一个位置的距离是到左侧最近0的距离，当前位置比它远一步）
            result[i] = result[i-1] + 1
    
    # 第二次遍历：从右到左，取当前值（左侧距离）和右侧最近0距离的最小值
    for i in range(n-2, -1, -1):
        result[i] = min(result[i], result[i+1] + 1)
    
    return result

原理说明 #

• 左到右遍历时，我们只关心左边最近的0，所以遇到0就重置距离为0，否则延续前一个位置的距离加1。
• 右到左遍历时，我们再考虑右边最近的0，用右侧位置的距离加1（当前位置到右侧最近0的距离），和之前的左侧距离取最小值，就能得到每个位置到最近0的距离。

测试你的例子：
输入[0, 1, 2, 0, 4, 5, 6, 7, 0, 5, 6, 9]，输出正好是[0, 1, 1, 0, 1, 2, 2, 1, 0, 1, 2, 3]，完全符合预期。

方法二：基于0的索引列表修正你的初始思路 #

如果你更倾向于用自己最初的思路——先收集所有0的索引再处理间隙，我们可以修正代码，让它考虑每个位置到前后两个0的距离，取最小值，同时处理数组开头和末尾的特殊情况。

修正后的代码 #

def get_empty_lot_index(arr: list) -> list:
    ''' Gets all indices of empty lots '''
    lots = []
    for i in range(len(arr)):
        if arr[i] == 0:
            lots.append(i)
    return lots

def space_to_empty_lots(arr: list) -> list:
    n = len(arr)
    empty_lots = get_empty_lot_index(arr)
    
    # 处理数组中没有0的特殊情况（根据需求调整，这里返回无穷大）
    if not empty_lots:
        return [float('inf')] * n
    
    new_arr = []
    first_zero = empty_lots[0]
    
    # 1. 处理数组开头到第一个0的部分（只能到第一个0）
    for i in range(first_zero + 1):
        new_arr.append(first_zero - i)
    
    # 2. 处理两个相邻0之间的部分（取到前后两个0的最小距离）
    for j in range(1, len(empty_lots)):
        left_zero = empty_lots[j-1]
        right_zero = empty_lots[j]
        # 遍历两个0之间的所有位置
        for i in range(left_zero + 1, right_zero + 1):
            dist_to_left = i - left_zero
            dist_to_right = right_zero - i
            new_arr.append(min(dist_to_left, dist_to_right))
    
    # 3. 处理最后一个0到数组末尾的部分（只能到最后一个0）
    last_zero = empty_lots[-1]
    for i in range(last_zero + 1, n):
        new_arr.append(i - last_zero)
    
    return new_arr

原理说明 #

• 开头到第一个0的部分：每个位置的距离就是第一个0的索引 - 当前索引，比如数组开头是[1,2,0]，1的距离是2，2的距离是1。
• 相邻0之间的部分：每个位置计算到左边0的距离和右边0的距离，取更小的那个，比如0在索引3和8之间，位置5到3的距离是2，到8的距离是3，所以取2。
• 最后一个0到末尾的部分：每个位置的距离是当前索引 - 最后一个0的索引，比如最后一个0在8，位置9的距离是1，位置11的距离是3。

这个方法同样能得到正确的结果，更贴合你最初的思考路径。

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