奇异点算法

Question

给定一个包含N个数字的集合，我需要找到其中的奇数。现在N是一个奇数，并且确定“奇数”方法是将给定的数字配对，最终你会剩下一个数字，这就是“奇数”。

这些数字根据它们之间的距离进行配对。首先，从给定的数字集中选择距离最小的两个数字并将它们配对。这样我们就有了N-2个数字。该过程重复进行，直到只剩下1个数字。

例如：{1,4,3}

1和3之间的距离为2，3和4之间的距离仅为1。因此，3和4配对，留下1个未配对的数字，即为奇数。

到目前为止，我能想到的是对给定列表进行排序，并找到每个数字之间的差异并消除配对，从最小距离开始。这最终会得到“奇数”，但问题必须使用具有小于O(N^2)复杂度的算法来解决。希望能给予正确方向的帮助。谢谢

另一个例子：{1,3,4,6,10}

最小差异对3,4 消除配对 -> {1,6,10} 最小差异对6,10 消除配对 -> {1} 是奇数

另一个例子 {2,4,1,10,8,9,6}

最小差异对(1,2) (8,9)和(9,10)。消除(1,2)和(8,9)或(10,9)任意一组都可以（对于相似的距离，结果可能会随机变化），我们选择(8,9) -> {4,10,6}

接下来消除(4,6) --> {10} 是奇数 注意：也可以选择(9,10)而不是(8,9)。

- Priyath Gregory

---

为什么你的示例没有考虑1和3？只有相邻元素才是候选项吗？ - amit

如果输入是前n个自然数，例如1、2、3、4、5、6、7、8、9，应该给出什么答案？ - Anil

如果我的集合是1、2、3、4、6。如果我配对2和3，那么我必须配对4和6，奇数是1，如果我配对1和2，3和4，奇数是6。哪个是正确答案？ - Anil

你的第二个例子正确吗？在消除 {3, 4} 后，你是如何得到剩下 {4, 6, 10} 的呢？难道不应该是 {1, 6, 10}，而 1 是其中的奇数吗？ - IVlad

@Anil 在这种情况下，没有一个正确答案，你可以选择任何一种方式。 - Priyath Gregory

Answer 1

一种可能的O(nlogn)解决方案如下：

1. 对数组进行排序（在O(nlogn)时间内）。
2. 计算排序后数组中相邻元素之间的差异。
3. 将差值（以及相应的对）存储在最小堆中。
4. 从最小堆中弹出顶部对。对于每个弹出的对，您将不得不添加另一个对到堆中。这将对应于从弹出的对开始的相邻元素。例如，如果数组是{...., 3, 5, 6, 9, ....}，并且弹出的对是{5,6}，则使用差值为6将另一对添加到堆中{3,9}。
5. 还要跟踪已经弹出的元素（可能在哈希表中），并拒绝任何已经弹出的元素组成的对。
6. 一旦堆为空，未包含在任何有效弹出对中的元素将是奇数个元素。

- Abhishek Bansal

---

@user269952，由于120是最右侧的元素，它的右侧没有元素，因此在这种情况下不会添加任何一对。 - Abhishek Bansal

我想我明白了。正在实施，会让你知道进展情况。谢谢。 - Priyath Gregory

第四步不会使复杂度变为O(N^2)吗？从堆中弹出元素，并在每次迭代中扫描数组以查找相邻的对，最后在堆中进行排序插入。 - Priyath Gregory

@user269952 不需要。除了存储成对的值之外，还要存储它们的索引。这样访问它们的邻居（如果存在）就是O(1)操作。 - Abhishek Bansal

正如我之前提到的，弹出一对元素后，您需要将相邻的一对元素插入回堆中。堆结构应确保新的一对元素落在其正确的位置上。 - Abhishek Bansal