Java 中从双精度数组中查找原始数组

这是一个在顶级 IT 公司（如 Google、Amazon、TCS、HCL、IBM 和 Accenture 等）面试中经常被问到的问题。通过解决这个问题，面试官希望检查面试者的逻辑能力、批判性思维和解决问题的能力。因此，在本节中，我们将使用不同的方法和逻辑来 在 Java 中从双倍数组中找到原始数组。此外，我们还将为此创建 Java 程序。

在这个问题中，一个整数数组 `original` 被转换为一个双倍数组 `changed`，方法是将 `original` 中每个元素的值加倍，然后随机打乱结果数组。

问题陈述

给定一个数组 `changed`，如果 `changed` 是双倍数组，则返回 `original`。如果 `changed` 不是双倍数组，则返回一个空数组。`original` 中的元素可以以任何顺序返回。

让我们通过一个例子来理解这个问题。

示例 1

假设我们有一个双倍数组 [1, 3, 4, 2, 6, 8]。检查该数组是否为原始数组。

为了检查给定数组是否为双倍数组，请将数组的每个元素乘以 2。如果结果元素存在于数组中，则表示给定数组是一个双倍数组，并且原始数组包含乘以 2 的元素。

第一个元素的两倍：1*2 = 2（存在于给定数组中）

第二个元素的两倍：3*2 = 6（存在于给定数组中）

第三个元素的两倍：4*2 = 8（存在于给定数组中）

我们观察到给定数组前三个元素的两倍已经存在于数组中，因此它是一个双倍数组，数组的原始元素是 [1, 3, 4]。

我们也可以将原始数组打乱为 [4, 3, 1] 或 [3, 1, 4]。

示例 2

让我们考虑另一个数组 [4, 2, 0, 1]。

第一个元素的两倍 4*2 = 8（不存在于给定数组中）

第二个元素的两倍 2*2 = 4（存在于给定数组中）

第三个元素的两倍 0*2 = 0（存在于给定数组中）

第四个元素的两倍 1*2 = 2（存在于给定数组中）

我们观察到三个元素的两倍存在于给定数组中。第一个元素的两倍 (8) 不存在于给定数组中。因此，原始数组将是一个空数组，因为 `changed` 不是一个双倍数组。

注意：如果数组只包含一个元素，则 `changed` 不是双倍数组。

问题解决方案

1. 首先，将给定数组按升序排序。
2. 创建一个队列数据结构。最初队列为空。
3. 创建另一个数组来存储结果数组。
4. 重复以下步骤，直到队列变空。
   1. 将第 i 个元素的两倍插入队列的前端。
   2. 取出给定数组的下一个元素，并将其与队列的第 i 个元素进行比较。
      • 如果元素已经存在，则将其从队列中删除。
      • 否则，将元素插入结果数组并移至下一个元素。
5. 打印结果数组。

让我们在 Java 程序中实现上述步骤。

Java 程序：从双倍数组中找到原始数组

该问题可以使用队列和 HashMap 数据结构来解决。

使用 HashMap

上述问题可以使用 HashMap 来解决。

FindOriginalArray.java

输出

The original array is: 1 2 2 4

同样的问题也可以使用队列数据结构来解决。其逻辑与上述方法略有不同。以下代码片段展示了使用队列解决问题的逻辑。

复杂度分析

上述解决方案的时间复杂度为 O(nlogn)，空间复杂度为 O(n)。