Java 中计数 OR 对

给定一个包含非负数的数组。另外，给定一个数字 K。我们的任务是计算给定数组中满足以下条件的数对的数量：数对中元素的 OR 运算结果大于 K。

示例 1

输入

int inArr1[] = {1, 3, 7, 9, 15, 20, 25}, K = 15

输出

11

解释

OR 运算结果大于 15 的数对是：(15, 20), (15, 25), (1, 20), (3, 20), (7, 20), (9, 20), (25, 20), (1, 25), (3, 25), (7, 25), (9, 25)。这些数对的数量是 11。因此输出是 11。

示例 2

输入

int inArr1[] = {0, 1, 5, 8, 10, 19, 15, 25, 30, 40, 45}, K = 35

输出

19

解释

OR 运算结果大于 35 的数对是：(0, 40), (1, 40), (5, 40), (8, 40), (10, 40), (19, 40), (15, 40), (25, 40), (30, 40), (45, 40), (0, 45), (1, 45), (5, 45), (8, 45), (10, 45), (19, 45), (15, 45), (25, 45), (30, 45)。这些数对的数量是 19。因此输出是 19。

简单方法

简单的方法是找到所有的数对，然后对数对中的元素进行 OR 运算。OR 值大于 K 的数对将使计数增加 1。计数的最终值就是我们的答案。

算法如下：

步骤 1：创建一个变量 'cntORPairs' 用于记录 OR 值大于 K 的数对数量。将其赋值为 0。

步骤 2：运行一个从 0 到 'len' 的循环（假设迭代器为 'j'）。

步骤 3：运行一个嵌套循环，从 'j' + 1 到 'len'（假设迭代器为 'k'）。

步骤 4：检查 'inputArr[j]' 和 'inputArr[k]' 的 OR 值是否大于 'K'。

步骤 5：将 'cntORPairs' 增加 1。

步骤 6：最后，返回 'cntORPairs'。

现在，请看下面的程序。

文件名：CountOrPair.java

输出

For the input array: 
1 3 7 9 15 20 25 
The total count of OR pairs whose value is greater than 15 is: 11


For the input array: 
0 1 5 8 10 19 15 25 30 40 45 
The total count of OR pairs whose value is greater than 35 is: 19

复杂度分析：程序使用嵌套 for 循环查找所有数对。总共有 (N * (N - 1)) / 2 个数对。因此，程序的整体时间复杂度为 O(N²)，其中 'N' 是输入数组的大小。此外，程序不使用额外的空间，因此空间复杂度为 O(1)。

数学方法

思路是找出大于 'K' 的元素的数量。大于 'K' 的元素可以与输入数组 inputArr[] 中的其他所有元素组成数对。这是因为，如果一个数字大于 'K'，那么它与任何元素的 OR 运算结果都将大于 'K'。

让我们举一个例子以更好地理解。

设数组为 inputArr[] : {15, 1, 2, 3}

设 'K' 为：7

'K' 的二进制表示是：0111

'inputArr[0]' 即 15 的二进制表示是：1111

'inputArr[1]' 即 1 的二进制表示是：0001

'inputArr[0]' 和 'inputArr[1]' 的 OR 值为：15 | 1 = 15，大于 7。OR 值大于 7 是因为第一个元素 15 大于 7。如果我们取两个小于 7 的数，它们的 OR 值永远不会大于 7。例如：inputArr[2] | inputArr[3] = 2 | 3 得到 3，小于 7。

请看下面的算法。

步骤 1：创建一个变量 'cntORPairs' 用于记录数对的数量。将其赋值为 0。

步骤 2：创建一个变量（例如 'cntK'）用于记录大于 K 的元素数量，并初始化为 0。

步骤 3：运行一个从 0 到 'N' 的循环（假设循环变量为 'j'）。

步骤 4：检查 'inputArr[i]' 是否大于 'K'。

• 将 'cntK' 增加 1。
• 将 'cntORPairs' 增加 ('N' - 'cntK')（我们可以与大于 'K' 的数字组成 'N' 个数对。但每次添加时需要减去 'cntK'，以避免重复计算数对）。

步骤 5：最后，返回 'cntORPairs'。

上述步骤的实现如下。

文件名：CountOrPair1.java

输出

For the input array: 
1 3 7 9 15 20 25 
The total count of OR pairs whose value is greater than 15 is: 11


For the input array: 
0 1 5 8 10 19 15 25 30 40 45 
The total count of OR pairs whose value is greater than 35 is: 19

复杂度分析：该程序使用单个循环，因此时间复杂度为 O(N)，其中 N 是输入数组的总元素数。程序空间复杂度为常数，即 O(1)。

注意：在许多情况下，上述方法可能会给出错误的结果。因此，为了使其正常工作，建议使用 K 的值为 2^p - 1。即 1, 3, 7, 15, 31… 等。我们看到在上面的例子中输出是正确的（尽管 K 不是 2^p - 1 的形式）。但是，不能保证它对任何 K 值都有效。因此，为了安全起见，请使用 K 的值为 2^p - 1。