分析算法复杂度，简化数据结构，使用并行或递归下降。
以上回复有部分引自免费微信小程序：皆我百晓生。 如问题尚未解决，还请稍待，如有疑问请回复进一步沟通。
为了优化这个程序，我们可以从以下几个方面进行改进：
-
减少嵌套循环：目前的实现中有两个嵌套循环，时间复杂度为O(N^2)，可以通过一些数据结构和预处理来降低这个复杂度。
-
使用位运算：题目要求的是计算具有相同二进制最高位的整数对的数量，我们可以在预处理阶段就找出每个二进制最高位，并存储起来。
以下是优化后的代码：
#include
#include
#include
#include
using namespace std;
int countPairs(vector& nums) {
unordered_map> groupByMSB;
for (int num : nums) {
int msbPosition = 31 - __builtin_clz(num); // 获取最高位位置
groupByMSB[msbPosition].push_back(num);
}
int result = 0;
for (const auto& entry : groupByMSB) {
const int msbPosition = entry.first;
const vector& numbersWithMSB = entry.second;
sort(numbersWithMSB.begin(), numbersWithMSB.end()); // 对同一MSB的数字排序
int distinctCount = 1;
long long productSum = numbersWithMSB[0];
for (size_t i = 1; i < numbersWithMSB.size(); ++i) {
if (numbersWithMSB[i] != numbersWithMSB[i - 1]) {
distinctCount++;
productSum *= numbersWithMSB[i];
} else {
productSum *= 2;
}
}
result += distinctCount * productSum;
}
return result;
}
int main() {
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector nums(n);
for (int i = 0; i < n; ++i) {
cin >> nums[i];
}
cout << countPairs(nums) << endl;
}
return 0;
}
在这个优化版本中，我们首先通过__builtin_clz函数找到每个数字的最高位（MSB）位置，并将这些数字分组。然后，对于每个MSB的组，我们对其进行排序，以便可以快速地确定唯一值的数量和它们的乘积。这样，我们只需要遍历每个组中的元素一次，大大减少了时间复杂度。整体上，这种方法的时间复杂度大约是O(N log N)。
注意：__builtin_clz是GCC和Clang编译器提供的一个内置函数，用于获取输入参数中最左边连续零的个数。如果你使用其他编译器，可能需要寻找替代方法，例如使用位操作或者标准库函数来实现类似功能。在C++20及以后的版本中，你可以使用std::countl_zero函数。
赞
回复
