给定一个 2D 正方形 (n*n) 矩阵，我试图找出是否有一种方法可以在小于 O(n^2) 的时间内对矩阵的上三角执行操作[最好是在线性时间内]。请注意，矩阵元素是连续的，如示例所示。即:每行和每列中的所有值都已排序。我已经使用 O(n^2) 复杂度解决了这个问题。下面的例子:
21 22 23 24 25
26 27 28 29 30
31 32 33 34 35
36 37 38 39 40
41 42 43 44 45
现在，如果我想对上三角执行异或运算，则意味着对以下元素进行异或运算: 21^22^23^24^25^26^27^28^29^31^32^33^36^37^41 = 35，这是想要的结果。
换句话说，我基本上是异或运算:
21 22 23 24 25
26 27 28 29
31 32 33
36 37
41
我试图通过生成二进制等价物来找到模式来使用 DP 来解决问题，但找不到任何一致的模式。
最佳答案
评论后编辑:
使用来自 this post 的方法
long long f(long long a) {
long long res[] = {a,1,a+1,0};
return res[a%4];
}
long long getXor(long long a, long long b) {
return f(b)^f(a-1);
}
像这样创建一个循环:
long FinalXor = 0;
for(int i = 0 ; i< n; i++){
FinalXor =FinalXor^getXor(m(i,0),m(i,0)+ n-i)
}
您只需要遍历每行的第一个值，生成复杂度为 O(n) 的算法
关于algorithm - 将矩阵运算优化到小于 O(n^2) 的复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40250010/