当我必须将算法从 O(n) 空间复杂度转换为 O(1) 空间复杂度时，我应该考虑什么技术？
例如，对于置换的构建数组（LeetCode问题）。 我正在考虑将这种BRUT前算法从O（N）转换为O（1）空间复杂性算法的临时变量。 （解决方案来自）。
BRUT力量算法。
class Solution:
def buildArray(self, nums: List[int]) -> List[int]:
res = []
for i in range(0, len(nums)):
res.append(nums[nums[i]])
return res
我找不到使用临时变量的解决方案。 相反，我发现人们这样做了：
O（1）空间复杂性算法。
class Solution:
def buildArray(self, nums: List[int]) -> List[int]:
n = len(nums)
for i in range(0, len(nums)):
nums[i]=nums[i]+(n*(nums[nums[i]]%n))
for i in range(0, len(nums)):
nums[i] = int(nums[i]/n)
return nums
我的问题，当我必须将算法从o（n）转换为o（1）空间复杂性时，我应该考虑什么技术？
For example for the Build Array from Permutation (LeetCode question).
I was thinking about temporary variable to transform this brut fore algorithm from O(n) to O(1)space complexity algorithm. (solutions are from dev.to).
A brut force algorithm.
class Solution:
def buildArray(self, nums: List[int]) -> List[int]:
res = []
for i in range(0, len(nums)):
res.append(nums[nums[i]])
return res
I couldn't find a solution using a temporary variable.
Instead, I found that people did this:
O(1) space complexity algorithm.
class Solution:
def buildArray(self, nums: List[int]) -> List[int]:
n = len(nums)
for i in range(0, len(nums)):
nums[i]=nums[i]+(n*(nums[nums[i]]%n))
for i in range(0, len(nums)):
nums[i] = int(nums[i]/n)
return nums
My question, to what technique should I think about when I have to transform an algorithm from O(n) to O(1) space complexity?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
如果算法占用
o（n）空间，则必须将空间用于某些目的；通常用于计算一些值，您以后可以很容易地查找。这通常会导致时间更高的复杂性。如果您放弃空间，例如，o（n）<代码> o（1），您可能必须确定更高的时间复杂性。考虑 prefix sum algorithm 。它采用
o（n）空间，但是我可以回答o（1）的后续查询。如果我不想使用o（n）空间，则查询将采用o（n）。因此，这是时间和空间复杂性之间的权衡。If an algorithm takes up
O(n)space, then it must be using the space for some purpose; usually for computing some value that you can readily look up later. This will usually lead to better time complexity. If you give up on space, say makeO(n)toO(1), you may have to settle for a higher time complexity.Consider prefix sum algorithm. It takes
O(n)space, but then I can answer subsequent queries inO(1). If I do not want to useO(n)space, then queries will takeO(n). So, it is a trade-off between time and space complexity.