查找一个数是另一个数的幂次倍数的 JavaScript 程序

---

查找一个数是另一个数的幂次倍数的 JavaScript 程序是一个涉及查找数字对的问题，其中一个数字是另一个数字的幂次倍数。在本教程中，我们将讨论如何编写 JavaScript 程序来解决此问题。我们将探索各种方法和算法来有效地找到这些对。此外，我们还将讨论这些算法的时间和空间复杂度，以全面了解主题。

因此，让我们深入了解并学习如何编写 JavaScript 程序来查找一对整数，其中一个数是另一个数的幂次倍数。

问题陈述

给定一个整数数组，我们必须找到数字对，其中一个数字是另一个数字的幂次倍数。让我们通过一些示例来理解这一点。

示例

示例 1 −

Input: const arr = [2, 4, 6, 8, 10];
Output: [ [2, 8], [4, 8], [2, 4] ]

解释 − 在给定的输入数组中，满足一个数字是另一个数字的幂次倍数条件的数字对如下所示：

2 and 8: 2 is a power multiple of 8 (2^3 = 8)
4 and 8: 4 is a power multiple of 8 (2^2 = 4 and 2^3 = 8)
2 and 4: 2 is a power multiple of 4 (2^1 = 4)

因此，程序应将这些对返回到一个数组中。

示例 2 −

Input: const arr = [3, 9, 27, 81, 5];
Output: [ [3, 9], [9, 27], [27, 81] ]

解释 − 在给定的输入数组中，满足一个数字是另一个数字的幂次倍数条件的数字对如下所示：

3 and 9: 3 is a power multiple of 9 (3^2 = 9)
9 and 27: 9 is a power multiple of 27 (3^2 = 9 and 3^3 = 27)
27 and 81: 27 is a power multiple of 81 (3^3 = 27 and 3^4 = 81)

因此，程序应将这些对返回到一个数组中。

现在，让我们探索各种方法和算法，以有效地找到一对数字，其中一个数字是另一个数字的幂次倍数：

方法 1：暴力法

查找一对数字的最简单方法之一，其中一个数字是另一个数字的幂次倍数，是使用嵌套循环。在这种方法中，我们可以遍历数组中所有可能的数字对，并检查一个数字是否为另一个数字的幂次倍数。这种方法的时间复杂度为 O(n^2)，因为我们正在检查所有可能的对。

方法 2：使用哈希

解决此问题的另一种方法是使用哈希。在这种方法中，我们可以创建一个哈希表来存储数组中的数字。然后，我们可以遍历数组并检查哈希表中每个数字是否具有相应的幂次倍数。这种方法的时间复杂度为 O(n)，因为我们只遍历数组一次。

方法 3：排序和二分查找

我们还可以通过对数组进行排序并使用二分查找来查找每个数字的幂次倍数来解决此问题。在这种方法中，我们首先对数组进行排序，然后遍历它以使用二分查找找到每个数字的幂次倍数。这种方法的时间复杂度为 O(n log n)，因为我们正在对数组进行排序并使用二分查找。

这些是一些可用于查找一对数字的方法，其中一个数字是另一个数字的幂次倍数。方法的选择取决于输入数组的大小和问题的时效性要求。因此，在本教程中，我们将使用暴力算法来使用 Javascript 解决问题。

暴力算法

输入 - 大小为 n 的整数数组 arr。

输出 - 一对数字的数组，其中一个数字是另一个数字的幂次倍数。

• 初始化一个空的数字对数组以存储结果对。

• 使用两个嵌套循环遍历数组 arr 中所有可能的数字对

-

• 对于每一对，检查一个数字是否为另一个数字的幂次倍数 -

• 使用模运算符 % 来检查一个数字除以另一个数字的余数是否为零。

• 如果余数为零，则表示一个数字是另一个数字的幂次倍数。

• 将数字对添加到 pairs 数组。

• 返回包含所有对的 pairs 数组，其中一个数字是另一个数字的幂次倍数。

现在，让我们借助一个示例来理解上述算法的实现，其中我们使用 Javascript 实现此算法。

示例

上述算法的实现

该程序使用暴力方法查找一对数字，其中一个数字是另一个数字的幂次倍数。它使用嵌套循环遍历输入数组中所有可能的数字对，并使用模运算符检查一个数字是否为另一个数字的幂次倍数。如果一对满足此条件，则将其添加到结果 pairs 数组中。但是，这种方法的时间复杂度为 O(n^2)，对于大型输入数组可能效率不高。

输入：[2, 4, 6, 8, 10]

预期输出：[ [ 2, 4 ], [ 2, 6 ], [ 2, 8 ], [ 2, 10 ], [ 4, 8 ] ]

function findPowerMultiplePairs(arr) {
   const pairs = [];
   const n = arr.length;
   
   // Iterate through all possible pairs of numbers
   for (let i = 0; i < n; i++) {
      for (let j = i + 1; j < n; j++) {
      
         // Check if one number is a power multiple of the other
         if ((arr[i] % arr[j] === 0) || (arr[j] % arr[i] === 0)) {
            pairs.push([arr[i], arr[j]]);
         }
      }
   }
   return pairs;
}

// Example usage:
const inputArray = [2, 4, 6, 8, 10];
const result = findPowerMultiplePairs(inputArray);
console.log(result);

结论

因此，我们学习了查找一对数字的 JavaScript 程序，其中一个数字是另一个数字的幂次倍数。我们讨论了一种暴力方法，该方法涉及遍历所有可能的数字对并检查幂次倍数条件。总的来说，了解问题并选择正确的方法对于有效地解决此类编程挑战至关重要。