优于朴素O(n*log(n))的解法：全1字符串剩余1定位问题

我这里有一个Python 3的朴素实现，还附带了步骤打印功能，能帮你清楚看到每一步的变化过程：

代码实现 #

def find_last_one_position(n):
    # 用列表存储（方便修改，字符串不可变）
    s = ['1'] * n
    current_pos = 0
    direction = 1  # 1代表从左到右，-1代表从右到左
    remaining = n

    print(f"初始状态: {' '.join(s)}")

    while remaining > 1:
        # 先移动到下一个要处理的位置
        current_pos += direction
        # 碰到边界就转向，调整到有效范围内
        if current_pos < 0 or current_pos >= n:
            direction *= -1
            current_pos += direction * 2

        # 找到可替换的'1'，执行替换
        if s[current_pos] == '1':
            s[current_pos] = '0'
            remaining -= 1
            print(f"步骤后状态: {' '.join(s)} | 剩余{remaining}个'1'")
            # 跳过下一个'1'，再次移动
            current_pos += direction
            # 处理移动后的边界问题
            while current_pos < 0 or current_pos >= n:
                direction *= -1
                current_pos += direction * 2

    # 定位最后一个'1'的索引（从0开始计数）
    last_pos = s.index('1')
    print(f"\n最后剩余的'1'位置（从0开始计数）: {last_pos}")
    return last_pos

# 测试示例
if __name__ == "__main__":
    # 测试长度为8的情况
    find_last_one_position(8)

代码逻辑说明 #

• 初始化：用列表替代字符串（因为字符串无法直接修改单个字符），用current_pos跟踪迭代器位置，direction控制移动方向，remaining记录剩余的'1'数量。
• 循环处理：
  1. 每次先移动到下一个位置，碰到字符串两端就反转方向，调整位置到有效区间内。
  2. 如果当前位置是'1'，就替换为'0'，更新剩余数量并打印当前状态。
  3. 完成替换后，跳过下一个'1'，再次移动位置，同样处理边界转向。
• 结果输出：循环结束后，找到列表中最后一个'1'的索引并返回。

示例输出（n=8时） #

初始状态: 1 1 1 1 1 1 1 1
步骤后状态: 0 1 1 1 1 1 1 1 | 剩余7个'1'
步骤后状态: 0 1 0 1 1 1 1 1 | 剩余6个'1'
步骤后状态: 0 1 0 1 0 1 1 1 | 剩余5个'1'
步骤后状态: 0 1 0 1 0 1 0 1 | 剩余4个'1'
步骤后状态: 0 0 0 1 0 1 0 1 | 剩余3个'1'
步骤后状态: 0 0 0 1 0 0 0 1 | 剩余2个'1'
步骤后状态: 0 0 0 0 0 0 0 1 | 剩余1个'1'

最后剩余的'1'位置（从0开始计数）: 7

这个解法逻辑直白，步骤透明，非常适合理解整个迭代过程。如果需要更高效的版本，还可以基于数学规律推导，但这个朴素实现用来搞懂问题本质最直观。

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