迭代列表时如何标记已使用索引？两种标记方案的空间复杂度疑问

1. 更高效的已使用标记方案 #

你当前使用独立marker列表的方案是通用场景下非常常见的实现，空间复杂度确实为O(n)。针对你正在求解的算法题场景（单个数组元素仅允许使用一次、数组长度通常不超过20），位掩码是公认更高效的实现方案：

• 用一个整数的二进制每一位代表对应索引的使用状态，例如第i位为1表示索引i的元素已被使用，为0表示未使用
• 所有操作均为位运算，执行速度远快于数组读写；当数组长度不超过32时仅需一个普通整数存储，长度不超过64时用长整型存储，空间复杂度为O(1)
• 天然适配回溯、状压DP等算法的状态传递逻辑，无需拷贝整个标记数组，直接传递整数即可，代码实现更简洁

2. 修改原数组结构的方案效果 #

该方案没有优化空间复杂度，也不可能达到O(1)：

• Python中元组为不可变类型，无法直接修改元组内的第二个数值，你需要替换为嵌套列表[[1,1],[2,1],...]才能实现标记修改，本身会引入额外开销
• 该方案本质只是把标记位和原数值存储在同一个结构中，总存储量仍和数组长度n成正比，空间复杂度依然是O(n)
• 额外弊端是修改原数组后如果需要用到原始数值，还需要额外做状态复原操作，代码复杂度高于独立标记方案，不推荐使用

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