统计异或值在范围内的数对有多少
难度:
标签:
题目描述
代码结果
运行时间: 252 ms, 内存: 18.7 MB
/*
* 思路:
* 1. 使用Java Stream的flatMap和filter方法来实现。
* 2. flatMap生成(i, j)的所有可能的组合,并计算其XOR值。
* 3. filter筛选出XOR值在[low, high]范围内的组合。
* 4. 计算符合条件的组合的数量。
*/
import java.util.stream.IntStream;
public class BeautifulPairsStream {
public int countBeautifulPairs(int[] nums, int low, int high) {
return (int) IntStream.range(0, nums.length)
.flatMap(i -> IntStream.range(i + 1, nums.length)
.map(j -> nums[i] ^ nums[j]))
.filter(xor -> xor >= low && xor <= high)
.count();
}
}
解释
方法:
该题解采用了基于计数和二分字典树(Trie)的思想,但实际上未使用树结构。算法通过逐位考察数字,并使用计数器来跟踪相同值的出现次数。对每一位的处理,算法检查当前位的0或1是否会让XOR结果在low和high范围内,并相应地更新计数器。对每个数字,都尝试与可能的XOR匹配进行配对,并调整答案计数。这种方法在处理每一位时都减少了不必要的计算,从而提高效率。
时间复杂度:
O(n log C)
空间复杂度:
O(n)
代码细节讲解
🦆
在该算法中,为什么要将`high`增加1来简化比较?这样做的具体原理是什么?
▷🦆
在题解中提到的`计数器`的使用方式是否意味着在每一位的处理过程中都会重新计算所有数字的计数?这种方法效率如何?
▷🦆
为什么在处理每一位时,需要检查`high & 1`和`low & 1`的值,并根据这些值来增加或减少计数?这种方法的逻辑基础是什么?
▷🦆
题解中提到的`nxt[x >> 1] += c`操作是如何帮助减少不必要的计算的?这一步骤在算法中起什么作用?
▷