Java 中检查 n 及其两倍是否存在

这是顶尖IT公司如Google、Amazon、TCS、HCL、IBM和Accenture等面试中经常遇到的问题。通过解决这个问题，可以考察应聘者的逻辑能力、批判性思维和解决问题的能力。因此，在本节中，我们将用不同的方法和逻辑来查找Java中的双数组中的原始数组。我们还将为此创建Java程序。

问题陈述

在这个问题中，我们得到了一个包含 n 个元素的数组。我们的任务是找到数组中一个元素的两倍也存在于数组中的元素。从数学上讲，a[i] = 2 * a[j]，其中 i < n 且 j < n，n 是输入数组的大小。请注意，i 可能等于也可能不等于 j。

让我们通过示例来理解。

示例 1

输入: numArr[] = {17, 11, 34, 10, 4, 9, 45}

输出: 输入数组中存在一个元素，其两倍也存在。

解释: 考虑输入数组的第一个和第三个元素，我们发现 numArr[2] = 2 * numArr[0]，即 34 = 2 * 17。

示例 2

输入: numArr[] = {7, 1, 3, 10, 4, 9, 15}

输出: 输入数组中不存在一个元素，其两倍也存在。

示例 3

输入: numArr[] = {7, 1, 3, 0, 4, 9, 5}

输出: 输入数组中存在一个元素，其两倍也存在。

解释: 考虑数组的第四个元素，我们发现 arr[3] = 2 * arr[3]，即 0 = 2 * 0。

朴素方法

最直接或朴素的方法是逐个检查每个元素，然后对该元素，遍历输入数组以找出其两倍是否存在。这将通过两个嵌套循环来完成。

算法

步骤 1: 从 j = 0 到 n 启动一个循环，其中 n 是元素的总数。检查 numArr[j] 是否等于 0。如果是 0，则返回 true。如果不是 0，则进入内循环（在步骤 2 中提及）。

步骤 2: 从 k = j + 1 到 n 启动另一个循环。在循环的每次迭代中，检查条件 numArr[j] == 2 * numArr[k] 或 2 * numArr[j] == numArr[k] 是否为真。如果为真，则存在一个元素，其两倍也存在于同一个数组中，并且可以立即终止循环。如果条件不为真，则转到下一个迭代，并再次检查条件。对于其他迭代也执行相同操作。如果外层循环终止，则数组中不存在一个元素，其两倍存在。

让我们在 Java 程序中实现上述算法。

检查 n 及其两倍是否存在于 Java 中的程序

文件名: DoubleEle.java

输出

For the input array: 
17 11 34 10 4 9 45 
There exists an element in the array whose double exists.

For the input array: 
7 1 3 10 4 9 15 
There is no any element in the array whose double exists.

For the input array: 
7 1 3 0 4 9 5 
There exists an element in the array whose double exists.

复杂度分析: 我们使用了嵌套的 for 循环来计算答案。因此，程序的时间复杂度为 O(n²)，其中 n 是输入数组中元素的总数。此外，我们没有使用任何数据结构来保存结果。因此，空间复杂度是常数，即 O(1)。

二分查找方法

在此方法中，我们将使用二分查找来查找元素的两倍。二分查找方法将比前一种方法更优化。

算法

步骤 1: 对输入数组进行排序。

步骤 2: 从 i = 0 到 n 启动一个循环。

步骤 3: 对于每次迭代，选择循环变量 i 指向的元素，并将其存储在一个变量中，在本例中为 currEle。

步骤 4: 将 currEle 的值加倍，并使用二分查找在已排序的数组中搜索这个加倍后的值。

• 如果找到了加倍后的值，则表示存在一个元素，其两倍存在于数组中，我们可以退出循环。
• 否则，请为其他迭代重复步骤 3。如果循环的所有迭代都已完成，则表示输入数组中不存在一个元素，其两倍存在。

让我们在 Java 程序中实现上述算法。

文件名: DoubleEle1.java

输出

For the input array: 
17 11 34 10 4 9 45 
There exists an element in the array whose double exists.

For the input array: 
7 1 3 10 4 9 15 
There is no any element in the array whose double exists.

For the input array: 
7 1 3 0 4 9 5 
There exists an element in the array whose double exists.

复杂度分析: 我们使用了一个循环来选择元素，该循环需要 O(n) 时间。此外，对于每次迭代，我们都使用了二分查找，它需要 O(log(n) 时间。因此，上述程序的总时间复杂度为 O(n * log(n))，其中 n 是数组中元素的总数。请注意，排序也需要 O(n * log(n)) 时间。但是，二分查找操作和排序操作不是嵌套的。因此，程序的总时间复杂度仍然相同。该程序占用常量空间。因此，上述程序的总空间复杂度为 O(1)。

方法：使用 HashSet

在此方法中，我们将逐个将元素存储在 HashSet 中。使用 contains 方法，我们将检查元素的两倍是否存在。

算法

步骤 1: 检查输入数组的第一个元素。如果为零，则完成，无需进一步操作。否则，转到下一步。

步骤 2: 创建一个哈希集并将输入数组的第一个元素插入其中。

步骤 3: 从 i = 1 到 n 启动一个循环，其中 n 是数组中的元素总数。

步骤 4: 检查循环变量 i 指向的数字的两倍或变量 i 指向的数字的一半是否存在于哈希集中。

• 如果存在，我们可以说数组中至少有一个数字，其两倍也可用，可以返回 true。
• 否则，检查变量 i 指向的数字是否为 0。如果是 0，则返回 true。
• 否则，将数字添加到哈希集中，然后转到下一个迭代并重复此步骤。如果循环的所有迭代都已完成，则意味着数组中没有一个元素，其两倍存在。因此，返回 false。

让我们在 Java 程序中实现上述算法。

文件名: DoubleEle2.java

输出

For the input array: 
17 11 34 10 4 9 45 
There exists an element in the array whose double exists.

For the input array: 
7 1 3 10 4 9 15 
There is no any element in the array whose double exists.

For the input array: 
7 1 3 0 4 9 5 
There exists an element in the array whose double exists.

复杂度分析: 我们只使用了一个循环。因此，上述程序的 time complexity 为 O(n)，其中 n 是数组中元素的总数。由于我们使用了哈希集数据结构来存储元素，因此程序的 total space complexity 为 O(1)。