java - 输出在 O(n) 时间和 O(1) 空间中取反的数组数字

Question

给定一个整数数组。如果数字 a 及其否定 -a 都存在于数组中，则打印它。例如：如果给出 {10, 5, 0, 9, -10, 7, -5} 则打印 10, 5。我给了面试官 O(N) 时间和 O(N) 基于 HashMap 的空间复杂度代码，但他进一步要求我在保持时间复杂度 O(N) 的最坏情况下将空间复杂度降低到 O(1)。注意：不允许计数排序。请问，谁能给我提供 O(1) 空间复杂度的方法？

标签： javaarraysalgorithmtime-complexityspace-complexity

Answer 1

如果数组元素是无序的并且在任意范围内，这在O(n)时间和空间上是不可能的。O(1)如果数组已排序，我们可以使用两个指针在这些约束内解决它。