数据结构
网络
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 次浏览
