4

我有以下问题：给定一个整数数组（最大大小为 50000），我必须找到最大 X 使得，

X = a[p] ^ a[p+1] ^ ... ... ^ a[q] for some p,q (p<=q)

我还必须找到 X 的最小值。

我试过这个过程，

sum[i] = a[0] ^ a[1] ^ ... ... ^ a[i] for some i .

我在 O(n) 中预先计算了它，并且

那么一些 X 的值p,q(p<=q)是 ,

X = sum[q] ^ sum[p-1]

MaxAns = Max of X for every pair of p,q (p<=q)

MinAns = Min of X for every pair of p,q (p<=q)

但是这个过程是O(n^2)。

如果没有 O(n^2) 算法，我怎么能做到这一点，效率更高？

4

3 回答 3

4

该算法仅适用于位宽有限的无符号整数。

  1. 计算每个数组元素的前缀总和（正如在 OP 中所做的那样）。
  2. 将每个前缀和添加到基数树（最高有效位对应于根，最低有效位对应于叶子）。
  3. 在计算sum[q]并将其添加到基数树之间，在部分构建的基数树中搜索 sum[q]（以获得 X 的最小值）。对于 X 的最大值，搜索~sum[q]。
  4. 如果树中缺少sum[q]（或）的任何位，请在 X 的最小/最大值中切换该位并继续向下搜索树。~sum[q]
  5. 获取为每个前缀找到的所有最小/最大值的最小值/最大值。

时间复杂度为 O(N log M)，其中 M 是数组元素的最大值。

于 2012-12-28T08:07:01.597 回答
1

这是完全错误的——不知道为什么，但一些测试似乎表明它是错误的。

我认为您可以从“Programming Pearls”的第 8 列中获得一些灵感，其中问题基本上是：“给定实数向量 x[n]，计算在任何连续子向量中找到的最大和”。

我认为您可以重用不同的算法，通过异或替换加法和减法（在此过程中保留了大多数有趣的属性：0 仍然是中性元素，异或是它自己的逆，可交换性）。

你可以找到幻灯片：http ://cs.bell-labs.com/cm/cs/pearls/s08.pdf但我绝对推荐这本书。

于 2012-12-28T03:49:53.513 回答
0

算法 ：

初始化：

ans=a[0]
cur=a[0]

循环遍历数组的每个元素：

(a) cur = max(a[i], cur^a[i])
(b) ans = max(cur, ans)
return ans

示例：设数组为 1 2 3 5 8 10

ans=cur=1

for i=1:

cur = max(2,3) = 3

ans = max(1,3) = 3


for i=2:

cur = max(3,0) = 3

ans = max(3,3) = 3


for i=3:

cur = max(5,6) = 6

ans = max(6,3) = 6


for i=4:

cur = max(8,14) = 14

ans = max(6,14) = 14


for i=5:

cur = max(10,4) = 10

anx = max(14,10) = 14

所以，ans = 14

这是我在 C++ 中的实现

int maxXOR(int a[], int n)
{
    int ans = a[0],cur=a[0];
    for(int i=1;i<n;i++)
    {
        cur=std::max(a[i],cur^a[i]);
        ans=std::max(ans,cur);
    }
    return ans;
}

分析 ：

Time Complexity : O(n)
Space Complexity : O(1)
于 2014-06-03T09:28:24.110 回答