c++ - 如何报告异或为零的子数组的索引?
问题描述
输入数组:5,2,7,100,1090,1,3,6,4,1062(0索引数组)
任务:对于给定的正整数序列,我想找到三元组 (i,j,k) 的数量,使得 1 ≤ i < j ≤ k ≤ N 并且
A[i]^…^A[j]−1=A[j]^A[j]+1^…^A[k],其中 ^ 表示按位异或。
我已经尝试在 C++ 中使用 prefix_xor 数组和映射来解决这个问题,但我仍然需要提高时间复杂度。
cin >> n;
int A[n];
ll count = 0;
unordered_map<int, vector<int>> map_table;
for (int i = 0; i < n; ++i)
cin >> A[i];
map_table[A[0]].push_back(0);
for (int i = 1; i < n; ++i)
{
A[i] = A[i] ^ A[i-1];
if (!A[i])
count += i;
map_table[A[i]].push_back(i);
}
unordered_map<int, vector<int>>::iterator i2;
for (i2 = map_table.begin(); i2 != map_table.end(); ++i2)
{
int size = i2->second.size();
if (size >= 2)
{
for (int i = 0; i < size-1; ++i)
{
for (int k = i+1; k < size; ++k)
count += ((i2->second[k])-(i2->second[i])-1);
}
}
}
cout << count << '\n';
在这个例子中,答案是 20
[0,2], [5,8], [0,9], [3,9]
异或(5, 2, 7) = 0; 异或(1, 3, 6, 4) = 0; XOR(100, 1090, .... 1062) = 0; 异或(5, 2, 7 .... 1062)= 0
解决方案
我将优化这部分代码:
for (int i = 0; i < size-1; ++i)
{
for (int k = i+1; k < size; ++k)
count += ((i2->second[k])-(i2->second[i])-1);
}
请注意,您基本上是在尝试查找数组 ( i2->second
) 中每对数字之间的差异之和。您正在执行此O(n^2)
操作,但如果我们稍微操作一下公式,我们可以更快地完成。
假设我们a
现在调用的数组有 length n
。我们现在只关注i
第 th 元素(索引为 0),我们将计算它被添加到总和中和从总和中减去的总次数。对于每一个j < i
,总和将包括a[i] - a[j]
。同样,对于每个j > i
,总和包括a[j] - a[i]
。在前一种情况下,a[i]
总共添加了i
次。在后一种情况下,a[i]
减去总n - i - 1
次数。a[i]
所以总和中的系数(添加的次数减去减去的次数)为i - (n - i - 1) == 2 * i - n + 1
。将它乘以每个元素并将所有内容相加就可以得到答案(在调整-1
部分之后)。
现在对于复杂性,该算法将O(n)
针对一个前缀 XOR 值,其中n
是该值出现的次数。由于每个前缀 XOR 值出现的次数之和将等于原始数组的长度,因此在创建映射后,总复杂度是线性的。
这是一个要求的例子:
假设数组有五个元素,a[0...4]
. 如果我们写出您要计算的总和,它看起来像这样:
(a[1] - a[0]) + (a[2] - a[0]) + (a[3] - a[0]) + (a[4] - a[0])
+ (a[2] - a[1]) + (a[3] - a[1]) + (a[4] - a[1])
+ (a[3] - a[2]) + (a[4] - a[2])
+ (a[4] - a[3])
我们稍后会处理-1
's。如果我们对类似的术语进行分组,它看起来像这样:
-4 * a[0] + -2 * a[1] + 0 * a[2] + 2 * a[3] + 4 * a[4]
请注意,通过上述公式,项的系数与该项的索引有关。因此,我们不是迭代每一对元素,而是计算这个缩短的表达式。在原始问题中,您需要为每对元素减去一个,因此我们可以从结果中减去元素对的数量。
推荐阅读
- jenkins - 如何在 src 中导入记录器模块并在所有 groovy 脚本中使用它?
- javascript - 尝试对我的表单进行实时计算时,我的总变量出现未定义变量错误
- http - Flutter http异常'(HttpException)=> Null'不是类型'(动态)=>动态'的子类型
- mysql - PHPMyAdmin Configuration not working because of MySQL user password?
- bixby - 自然语言类别如何确定胶囊是否了解新闻主题?
- r - 调用 library(raster) 或 require(raster) 导致 Rstudio 中止会话
- google-sheets - 引用存储在另一个单元格/命名范围中的 IMPORTRANGE() 函数?
- java - 如果 canvas.scale(x,y) 那么 canvas.drawPath(path,paint) 边缘模糊?
- pandas - 将 pd.NaT 转换为 timedelta
- java - 发送列表
通过 KSoap