Java 中的双倍对数组问题

这是一个在像谷歌、亚马逊、TCS、埃森哲等顶尖 IT 公司面试中经常被问到的问题。通过解决这个问题，面试官希望考察面试者的逻辑能力、批判性思维和解决问题的能力。因此，在本节中，我们将用不同的方法和逻辑来解决Java 中的检查数组能否形成二倍数对问题。我们还将为此创建 Java 程序。

问题陈述

在这个问题中，我们给定一个偶数长度的整数数组（arr[]）。我们需要检查是否可以重新排序数组，使其必须满足以下条件：

对于每一个 0 < = I < len(arr)/2

如果满足以上条件，则返回 true，否则返回 false。

示例 1

输入： a[] = [1, 2, 3, 4, 5, 6, 7]

输出： false

示例 2

输入： a[] = [1, 4, 8, 12, 14, 18]

输出： false

示例 3

输入： a[] = [4, -2, 2, -4]

输出： true

解释： 我们可以取两组，[-2, -4] 和 [2, 4]，来组成 [-2, -4, 2, 4] 或 [2, 4, -2, -4]。

让我们用一个简单的方式来理解这个问题。

假设，x 是一个数组中绝对值最小的元素，那么必须存在一个与其配对的元素 2*x，因为不存在任何其他元素 x/2 可以与它配对。

让我们按绝对值顺序检查元素。当我们检查一个元素 x 并且它还没有被使用时，它必须与 2*x 配对。我们将尝试写出 x, 2x。如果我们失败了，则返回 false。如果我们成功写出了所有配对，则返回 true。为了跟踪我们尚未写出的元素，可以使用一个 count 变量来存储它。

让我们通过示例来理解。

示例

情况1： 如果数组包含正数元素

考虑一个数组 [2, 4, 4, 8]。我们有一个 x = 2，需要将它与一个 2x = 4 匹配。然后一个 4 被用掉了，我们还有另一个 x = 4。我们需要将它与一个 2x = 8 匹配。没有其他元素需要匹配了。

在这个数组中，我们选择了数组的第一个元素，因为它是数组中最小的元素，并且没有 x/2 留下。所以，我们需要找到 2x。

情况2： 如果数组包含负数元素

一种方法是从最大的元素（绝对值最小）开始，并应用相同的逻辑（如上）。另一种方法是，从最小的元素（绝对值最大）开始，并尝试在每一轮中找到 x/2。

说明

1. 统计所有数字的个数。
2. 按绝对值顺序遍历所有数字。我们有 count[x] 个 x，所以我们需要相同数量的 2x 来与它们匹配。
3. 如果 count[x] > count[2 * x]， 那么我们返回 false。
4. 如果 count[x] <= count[2 * x]， 那么我们执行 count[2 * x] -= count[x] 来移除已匹配的 2x。

这里，我们不需要关心 0。它不符合上述逻辑，但不会破坏算法。

• 如果 count[0] 是奇数，它最终将无法匹配。（无论如何，我们可以在这里提前返回 false）
• 如果 count[0] 是偶数，我们仍然有 count[0] <= count[2 * 0]。并且我们仍然需要检查所有其他数字。

算法

1. 使用自定义比较器对给定数组进行排序。
2. 创建一个自定义比较器函数 `compare`，根据两个数字的绝对值来比较它们。
3. 初始化一个映射 `frequency`。
4. 遍历数组 'ARR'，并为每个数组元素的每次出现增加一次计数。
5. 再次遍历数组并添加以下条件：
   • 如果与 'ARR[i]' 作为键关联的值为零，则继续。
   • 如果与 2 * 'ARR[i]' 作为键关联的值为零，则返回 false。
   • 否则，在映射中将 'ARR[i]' 和 2 * 'ARR[i]' 作为键的计数值各减一。

检查数组能否形成二倍数对的 Java 程序

DoubledPair1.java

输出

false

让我们看看相同的另一个逻辑。

DoubledPair2.java

输出

true

复杂度分析

运行时间为 O(N * logN)，构建树形图是运行时间的主要部分。