資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究JavaScript 程式：求 XOR 為零的唯一三元組數量
求 XOR 為零的唯一三元組數量的 JavaScript 程式是一個常見的程式設計問題，它要求在給定陣列中找到 XOR 等於零的唯一三元組的數量。XOR 操作是一個按位運算子，它接收兩個位並返回 1（如果位不同）或 0（如果位相同）。在這個問題中，我們需要找到陣列中所有可能的三個數字組合，其中三元組的 XOR 為零。這個問題可以使用多種方法解決，包括暴力破解、雜湊和排序。在本教程中，我們將使用 JavaScript 中的雜湊技術提供該問題的分步解決方案。我們還將討論解決方案的時間和空間複雜度，並提供示例程式碼以更好地理解。讓我們開始吧！
問題陳述
我們需要在給定陣列中找到 XOR 等於零的唯一三元組的數量。換句話說，我們需要找到陣列中所有可能的三個數字組合，其中三元組的 XOR 為零。讓我們透過示例來理解這一點。
示例
示例 1 −
Input: arr = [4, 7, 5, 8, 3, 9] Output: 1
解釋 − 在此示例中，只有一個 XOR 等於零的唯一三元組。
即 [4, 7, 3]。
示例 2 −
Input: arr = [1, 3, 5, 10, 14, 15] Output: 2
解釋 − 在此示例中，有兩個 XOR 等於零的唯一三元組。
它們是 [1, 14, 15] 和 [5, 10, 15]。
好的，在我們理解了問題陳述後，是時候將重點轉移到解決此問題的各種方法上，然後選擇最合適的一種。
暴力破解 − 暴力破解方法涉及找到陣列中所有可能的三元組並檢查它們的 XOR 是否等於零。但是，對於大型陣列，此方法不可行，因為它具有 O(n^3) 的時間複雜度。
排序 − 排序方法涉及對陣列進行排序，然後使用雙指標方法找到 XOR 為零的三元組。由於排序，此方法具有 O(n^2logn) 的時間複雜度，但可以使用雜湊表最佳化為 O(n^2)。
雜湊 − 雜湊方法涉及使用雜湊表儲存陣列中元素的頻率。然後，我們可以遍歷所有可能的元素對，並檢查它們的 XOR 是否存在於雜湊表中。如果存在，我們將該 XOR 值的頻率新增到我們的答案中。此方法具有 O(n^2) 的時間複雜度和 O(n) 的空間複雜度。
總的來說，雜湊方法是解決此問題的最有效方法，因為它具有 O(n^2) 的時間複雜度，並且只需要 O(n) 的空間。這使得它適用於大型陣列，在大型陣列中暴力破解方法不可行。此外，雜湊方法不需要排序，這使得它比此問題的排序方法更快。因此，我們將在本教程中使用雜湊技術來解決此問題。
現在讓我們瞭解一下用於實現此問題的雜湊演算法。
雜湊演算法
定義一個名為 countTriplets 的函式，它有兩個引數：一個整數陣列及其大小。
建立一個空陣列 s。
遍歷陣列並將所有元素推入陣列 s 中。
將名為 count 的變數初始化為 0。
遍歷陣列，對於索引 i 處的每個元素，遍歷陣列中 i 之後的所有元素，從索引 j = i + 1 到 n-1。
計算 a[i] 和 a[j] 的 XOR 並將其儲存在變數 xr 中。
檢查 xr 是否存在於陣列 s 中，如果 xr 不等於 a[i] 且 xr 不等於 a[j]，則將 count 增加 1。
兩個迴圈完成後，將 count 除以 3 並返回結果。
在驅動程式程式碼中，定義一個數組 a 及其大小 n。
使用陣列 a 及其大小 n 作為引數呼叫 countTriplets 函式，並將結果儲存在名為 result 的變數中。
在我們理解了演算法之後，現在需要使用 JavaScript 來實現此演算法。因此，讓我們藉助示例使用 JavaScript 來執行此演算法。
示例：使用 JavaScript 實現雜湊方法
該程式計算陣列中 XOR 等於零的唯一三元組的數量。它透過使用雜湊技術來做到這一點，具體來說，是建立一個輸入陣列的集合以快速檢查是否存在值，然後遍歷所有值對並檢查它們的 XOR 是否存在於集合中。如果存在，則遞增計數。最終計數除以 3 以獲得唯一三元組的數量。
// JavaScript program to count the number of unique triplets whose XOR is 0 function to count the number of unique triplets whose XOR is 0
function countTriplets(arr) {
const n = arr.length;
// To store values that are present
const set = new Set(arr);
// stores the count of unique triplets
let count = 0;
// traverse for all i, j pairs such that j>i
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
// xor of a[i] and a[j]
const xr = arr[i] ^ arr[j];
// if xr of two numbers is present, then increase the count
if (set.has(xr) && xr !== arr[i] && xr !== arr[j])
count++;
}
}
// returns answer
return Math.floor(count / 3);
}
// Driver code
const arr = [1, 3, 5, 10, 14, 15];
console.log(countTriplets(arr));
結論
總而言之，我們已經瞭解瞭如何解決計算陣列中 XOR 為零的唯一三元組數量的問題。我們探索了各種方法，包括暴力破解、排序和雜湊。在這些方法中，雜湊技術在時間複雜度方面提供了最有效的解決方案。我們還使用 JavaScript 實現了雜湊技術並透過示例對其進行了驗證。需要注意的是，此問題在密碼學和資料壓縮等許多現實世界應用中都有應用。透過理解此問題及其解決方案，我們可以更好地理解 JavaScript 等程式語言的功能和多功能性。
157 次瀏覽
