遍历列表时如何将索引标记为 'used'？
How can I mark an index as 'used' when iterating over a list?
我将多次遍历 list of integers, nums,，每次当某个整数已 'used' 时（无关紧要），我想将索引标记为已使用.所以在以后的迭代中，我不会再使用这个整数。
两个问题：
我的想法是简单地创建一个单独的列表marker = [1]*len(nums)；每次我在 nums 中使用数字时，我都会从标记中的相应索引中减去 1，以此来跟踪我使用过的 nums 中的数字。
我的第一个问题是，是否有众所周知的有效方法来做到这一点？我相信这会使 SPACE 复杂度 O(n)
我的另一个想法是像这样替换 nums 中的每个条目。 nums = [1,2,3,4] -> nums = [(1,1),(2,1),(3,1),(4,1)]。每次我在 nums 中使用一个整数时，我都会从每对中的第二个索引中 subtract 1 作为标记它已被使用的一种方式。我的问题是，我是否正确理解这将优化 SPACE 相对于上述解决方案 1 的复杂性？ SPACE 复杂度为 O(1)?
作为参考，我正在解决以下问题：https://leetcode.com/contest/weekly-contest-256/problems/minimum-number-of-work-sessions-to-finish-the-tasks/
其中 tasks 中的每个条目需要使用一次。
我认为在 O(1) space 中没有办法做到这一点。虽然，我相信使用布尔值而不是整数值或使用集合的概念会是更好的解决方案。
不，space 复杂度仍然是 O(n)。这样想吧。让我们假设 n 是列表的大小。在您提到的第一种方法中，我们分别存储 n 'stuff' 。因此，space 复杂度为 O(n)。同样在第二种方法中，我们单独存储 n 'stuff' 。只是那些 n 'stuff' 被存储为同一个数组的一部分。因此，space 复杂度仍然保持不变，即 O(n)。
首先，在这两种情况下，space 复杂度都是 O(n)。这是因为无论您是否使用单独的列表来存储元素的使用，nums 本身都会使用 O(n) space。所以 space 复杂度在任何方面都不能归结为 O(1)。
但是，这里有一个建议。
如果您不想再次使用已使用的元素，那么为什么不将其从列表中删除。
或者，如果您不想破坏索引，只需将数字更改为 -1。
我将多次遍历 list of integers, nums,，每次当某个整数已 'used' 时（无关紧要），我想将索引标记为已使用.所以在以后的迭代中，我不会再使用这个整数。
两个问题：
我的想法是简单地创建一个单独的列表
marker = [1]*len(nums)；每次我在 nums 中使用数字时，我都会从标记中的相应索引中减去 1，以此来跟踪我使用过的nums中的数字。 我的第一个问题是，是否有众所周知的有效方法来做到这一点？我相信这会使 SPACE 复杂度 O(n)我的另一个想法是像这样替换 nums 中的每个条目。
nums = [1,2,3,4]->nums = [(1,1),(2,1),(3,1),(4,1)]。每次我在 nums 中使用一个整数时，我都会从每对中的第二个索引中subtract 1作为标记它已被使用的一种方式。我的问题是，我是否正确理解这将优化 SPACE 相对于上述解决方案 1 的复杂性？ SPACE 复杂度为 O(1)?
作为参考，我正在解决以下问题：https://leetcode.com/contest/weekly-contest-256/problems/minimum-number-of-work-sessions-to-finish-the-tasks/
其中 tasks 中的每个条目需要使用一次。
我认为在 O(1) space 中没有办法做到这一点。虽然，我相信使用布尔值而不是整数值或使用集合的概念会是更好的解决方案。
不，space 复杂度仍然是 O(n)。这样想吧。让我们假设 n 是列表的大小。在您提到的第一种方法中，我们分别存储 n 'stuff' 。因此，space 复杂度为 O(n)。同样在第二种方法中，我们单独存储 n 'stuff' 。只是那些 n 'stuff' 被存储为同一个数组的一部分。因此，space 复杂度仍然保持不变，即 O(n)。
首先，在这两种情况下，space 复杂度都是 O(n)。这是因为无论您是否使用单独的列表来存储元素的使用，nums 本身都会使用 O(n) space。所以 space 复杂度在任何方面都不能归结为 O(1)。 但是，这里有一个建议。 如果您不想再次使用已使用的元素，那么为什么不将其从列表中删除。 或者，如果您不想破坏索引，只需将数字更改为 -1。