子数组的大异或和问题

作者：Grey

创新互联是一家集网站建设,噶尔企业网站建设,噶尔品牌网站建设,网站定制,噶尔网站建设报价,网络营销,网络优化,噶尔网站推广为一体的创新建站企业，帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿，时刻以成就客户成长自我，坚持不断学习、思考、沉淀、净化自己，让我们为更多的企业打造出实用型网站。

原文地址：

博客园：子数组的大异或和问题

：子数组的大异或和问题

题目描述

数组中所有数都异或起来的结果，叫做异或和。给定一个数组 arr，其中可能有正、有负，有零，返回 arr 的大子数组异或和

题目链接见：牛客-子数组的大异或和

暴力解

枚举每个子数组的异或和，抓取全局大值返回，整个算法时间复杂度 O ( N 3 ) O(N^3) O(N3)，整个过程比较简单，不赘述，基于这个暴力解法，可以有优化一些的算法，就是利用前缀异或和数组，时间复杂度可以减少到 O ( N 2 ) O(N^2) O(N2)，思路如下

第一步

申请一个和原始数组一样长的前缀异或和数组

int[] eor = new int[arr.length];

其中eor[i]表示原始数组 0 位置到 i 位置的异或和是多少，实现代码如下：

eor[0] = arr[0];
    for (int i = 1; i< n; i++) {  eor[i] = eor[i - 1] ^ arr[i];
    }

有了 eor 数组以后，对于任意 i 位置，0 到 i 区间的异或和就可以直接获取到了，接下来是枚举数组中任意两个位置 i 和 j 区间的异或和，由于

i ~ j 之间的异或和等于eor[j] ^ eor[i-1](i >0)，所以

任何两个位置之间的异或和信息可以通过如下代码求得，其中 max 是全局异或和的大值

for (int i = 1; i< n; i++) {  max = Math.max(max, eor[i]);
      for (int j = i; j< n; j++) {max = Math.max(max, eor[j] ^ eor[i - 1]);
      }
    }

完整代码如下

public static int maxEor1(int[] arr, int n) {int[] eor = new int[arr.length];
    int max = arr[0];
    eor[0] = arr[0];
    for (int i = 1; i< n; i++) {  eor[i] = eor[i - 1] ^ arr[i];
    }
    for (int i = 1; i< n; i++) {  max = Math.max(max, eor[i]);
      for (int j = i; j< n; j++) {max = Math.max(max, eor[j] ^ eor[i - 1]);
      }
    }
    return max;
  }

整个算法复杂度是 O ( N 2 ) O(N^2) O(N2)，并不是最优解。

最优解

根据上述暴力解法，时间复杂度比较高的部分是：

当确定了 0 ~ i 位置的异或和以后，如何定位 0 ~ j 这个区间，使得 j ~ i 之间的异或和大。

暴力解法使用的是遍历的方式，而最优解，可以使用前缀树进行加速匹配，关于前缀树的内容，可以参考：前缀树的设计和实现

以数组[11,1,15,10,13,4]为例，我们把其前缀异或和数组转换成二进制，结果如下(其中eor[i…j]表示i~j的异或和)

eor[0…0] = 1011

eor[0…1] = 1010

eor[0…2] = 0101

eor[0…3] = 1111

eor[0…4] = 0010

eor[0…5] = 0110

把这些前缀异或和加入前缀树,

接下来，对于任何一个eor[i](0~i的异或和)来说，进入前缀树以后，前缀树需要快速找到和其匹配的eor[j]，使得i~j之间的异或和大，规则就是最高位（符号位）期待一样，紧着高位要期待不一样的值

例如：

eor[2] = 0101

eor[2] 期待和它符号位一样为0的值，紧着高位（由于前面28都是0，所以不存在和它符号不一样的，只看最后4位，

通过这个贪心，就可以在 O ( 1 ) O(1) O(1)时间复杂度直接得到结果。

说明：如果期待遇到 0 可是前缀树没有往 0 方向的路，那直接返回 1 即可，反之亦然。

完整代码如下

public static int maxEor(int[] arr, int n) {int[] eor = new int[arr.length];
    int max = 0;
    eor[0] = arr[0];
    for (int i = 1; i< n; i++) {  eor[i] = eor[i - 1] ^ arr[i];
    }
    Trie trie = new Trie(eor);
    trie.add(eor[0]);
    for (int i = 1; i< n; i++) {  max = Math.max(max, trie.get(eor[i]));
    }
    return max;
  }

  public static class Trie {public Node head;

    public Trie(int[] arr) {  head = new Node();
      for (int eor : arr) {add(eor);
      }
    }

    public void add(int num) {  Node cur = head;
      for (int bit = 31; bit >= 0; bit--) {int i = ((num >>>bit) & 1);
        if (cur.next[i] == null) {  cur.next[i] = new Node();
        }
        cur = cur.next[i];
      }
    }

    public int get(int eor) {  int expect = 0;
      Node cur = head;
      for (int bit = 31; bit >= 0; bit--) {// 符号位期待一样的
        // 非符号位期待相反的
        int expectBit = bit == 31 ? ((eor >>>bit) & 1) : (eor >>>bit & 1 ^ 1);
        if (cur.next[expectBit] != null) {  expect = ((expectBit<< bit) | expect);
          cur = cur.next[expectBit];
        } else {  expectBit = (expectBit ^ 1);
          cur = cur.next[expectBit];
          expect = ((expectBit<< bit) | expect);
        }
      }
      return expect ^ eor;
    }
  }

  public static class Node {public Node[] next = new Node[2];
  }

整个算法时间复杂度 O ( N ) O(N) O(N)，最优解。

更多

算法和数据结构笔记

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

网页标题：子数组的最大异或和问题-创新互联
URL链接：http://kswjz.com/article/cegdjc.html