子數組的大異或和問題

作者：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元起，快前往官網查看詳情吧

當前題目：子數組的最大異或和問題-創新互聯
地址分享：http://www.yijiale78.com/article22/cegdjc.html

成都網站建設公司_創新互聯，為您提供移動網站建設、電子商務、App開發、網站維護、網站排名、網站制作

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯