查詢一個數是另一個數的冪次倍數的 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 程式，其中一個數字是另一個數字的冪次倍數。我們討論了一種暴力方法，該方法涉及遍歷所有可能的數字對並檢查冪次倍數條件。總的來說，瞭解問題並選擇正確的方法對於有效地解決此類程式設計挑戰至關重要。