java - 数组唯一元素和移动应用程序数据结构

Question

最近在采访中提出了以下问题

1. 给定一个整数数组，其中除一个元素仅出现一次外，所有元素都重复两次，您需要以 O(nlogn) 时间复杂度找到唯一元素。假设数组是{2,47,2,36,3,47,36}，这里的输出应该是3。我告诉我们可以执行合并排序(因为它需要(nlogn))，然后我们可以检查下一个元素，但他说这将需要 O(nlogn)+ O(n)。我还告诉我们可以使用 HashMap 来记录元素计数，但他再次拒绝，因为我们必须再次迭代 hashmap 才能获得结果。经过一些研究，我发现使用异或运算将在 O(n) 中给出输出。除了排序之外还有没有更好的解决方案可以在 O(nlogn) 时间内给出答案？
2. 当我们使用智能手机时，我们可以一次打开许多应用程序。当我们查看当前打开的所有应用程序时，我们会看到一个列表，其中最近打开的应用程序位于前面，我们可以从列表中的任何位置删除或关闭应用程序。 java 中有一些可用的 Collection 可以以非常有效的方式执行所有这些任务。我告诉我们可以使用 LinkedList 或 LinkedHashMap 但他不相信。什么是最好使用的集合？

Answer 1

1. 首先，如果面试官使用 Big-O 表示法并期望得到 O(n log n) 解决方案，那么您的答案没有任何问题。我们知道O(x + y) = O(max(x, y))。因此，虽然你的算法是O(n log n + n)，但我们只要调用O(n log n)就可以了。但是，使用二分搜索可以在 O(log n) 内找到排序数组中出现过一次的元素。作为提示，在执行搜索时利用奇数和偶数索引。另外，如果面试官期望一个 O(n log n) 解决方案，那么反对遍历就是荒谬的。 HashMap 的解决方案已经是O(n)，如果这有问题的话，那就是需要额外的空间。因此，最好的方法是使用您提到的 XOR。还有一些 O(n) 解决方案，但它们并不比 XOR 解决方案更好。
2. 对我来说，LinkedList 也适合用于此任务。我们想要从任何位置删除，并且还想要使用一些堆栈操作(push、pop、peek)。可以从 LinkedList 构建自定义堆栈。