Java 中的 GP 序列问题数量

Java 中的 GP 序列问题涉及确定给定数字集中有效几何级数序列的数量。几何级数由公比定义，在各个领域都至关重要。在本教程中，我们将找到长度为 3 的 GP 序列的计数。

示例 1

输入: inputArray[] = {1, 2, 6, 2, 3, 6, 9, 18, 3, 9}, commonRatio = 3

输出: 公比为 3 的长度为 3 的 GP 子序列计数为：6

解释: 程序计算出在指定数组中有 6 个公比为 3 的长度为 3 的几何级数 (GP) 子序列。

示例 2

输入: inputArray[] = {1, 3, 9, 27, 81}, commonRatio = 3

输出: 公比为 3 的长度为 3 的 GP 子序列计数为：3

解释: GP 子序列为 {1, 3, 9}, {3, 9, 27}, 和 {9, 27, 81}。

方法：朴素方法

在朴素方法中，算法遍历数组中的每个元素三元组，检查它们是否构成一个几何级数子序列。三重嵌套迭代导致三次时间复杂度，由于其详尽的性质，对于较大的输入规模效率较低。

算法

步骤 1: 初始化两个 HashMap：创建左侧和右侧 HashMap，以计数数组中当前元素左侧和右侧的每个元素的出现次数。

步骤 2: 填充右侧 HashMap：遍历数组，并用每个元素的计数填充右侧 HashMap。

步骤 3: 通过遍历每个数组元素来计算 GP 子序列。

步骤 4: 对于当前元素 array[i]

步骤 4.1: 如果 array[i] 能被比率整除，则使用左侧 HashMap 计算 countLeft。

步骤 4.2: 减少右侧 HashMap 中 array[i] 的计数。

步骤 4.3: 确定 right HashMap 中 array[i] * ratio 的 countRight。

步骤 4.4: 将 countLeft 和 countRight 相乘以更新总子序列计数（结果）。

步骤 4.5: 增加左侧 HashMap 中 array[i] 的计数。

步骤 6: 返回总计数：遍历数组后，返回子序列的总计数（结果）。

实施

文件名: MyGPProgram.java

输出

The count of GP subsequences with length 3 and common ratio 3 is: 6

时间复杂度: 时间复杂度为 O(n)，因为它利用了两个遍历输入数组的循环，并且每个循环内的操作是常数时间的，从而实现了线性的整体时间复杂度。

辅助空间: 辅助空间复杂度为 O(n)，因为代码使用了两个 HashMap 来维护元素的计数，并且这些 HashMap 所需的空间与输入数组的大小成线性关系。

方法：计算几何级数 (G.P.) 子序列

该代码采用一种计算几何级数 (G.P.) 子序列的方法，利用哈希映射来跟踪元素出现次数，并根据给定的比率有效地计算计数。此外，代码还利用二项式系数来计算组合，从而提高了 G.P. 子序列计数的准确性。

算法

步骤 1: 在 binomialCoeff 中使用动态规划计算二项式系数 (n choose k)。

步骤 2: 在 countGPSubsequences 中，使用 left 和 right HashMaps 来跟踪当前元素左侧和右侧元素的计数。

步骤 3: 如果比率为 1，则使用二项式系数为每个元素的计数计算 GP 子序列。

步骤 4: 如果不为 1，则遍历数组

• 如果当前元素能被比率整除，则根据 left HashMap 更新 leftCount。
• 根据右侧 HashMap 中元素乘以比率的值调整 rightCount。
• 使用 leftCount 和 rightCount 更新总子序列计数。
• 相应地更新 left 和 right HashMaps 中的计数。

步骤 5: 定义数组、大小和公比。调用 countGPSubsequences 并打印结果。

实施

文件名: GPSequence.java

输出

Count of GP subsequences with commonRatio 3: 6

时间复杂度: countGPSubsequences 中的外部循环遍历所有数组元素一次，因此时间复杂度为 O(n)，其中 n 是输入数组的大小。

辅助空间: 空间复杂度受两个哈希映射（左侧和右侧）的影响。在最坏的情况下，当所有元素都唯一时，空间复杂度为 O(n)，因为每个元素可能在两个哈希映射中都有一个条目。