子數(shù)組的大異或和問題

作者：Grey

創(chuàng)新互聯(lián)是一家集網(wǎng)站建設(shè),噶爾企業(yè)網(wǎng)站建設(shè),噶爾品牌網(wǎng)站建設(shè),網(wǎng)站定制,噶爾網(wǎng)站建設(shè)報(bào)價(jià),網(wǎng)絡(luò)營銷,網(wǎng)絡(luò)優(yōu)化,噶爾網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強(qiáng)企業(yè)競爭力?？沙浞譂M足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時(shí)我們時(shí)刻保持專業(yè)、時(shí)尚、前沿，時(shí)刻以成就客戶成長自我，堅(jiān)持不斷學(xué)習(xí)、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實(shí)用型網(wǎng)站。

原文地址：

博客園：子數(shù)組的大異或和問題

：子數(shù)組的大異或和問題

題目描述

數(shù)組中所有數(shù)都異或起來的結(jié)果，叫做異或和。給定一個(gè)數(shù)組 arr，其中可能有正、有負(fù)，有零，返回 arr 的大子數(shù)組異或和

題目鏈接見：?？?子數(shù)組的大異或和

暴力解

枚舉每個(gè)子數(shù)組的異或和，抓取全局大值返回，整個(gè)算法時(shí)間復(fù)雜度 O ( N 3 ) O(N^3) O(N3)，整個(gè)過程比較簡單，不贅述，基于這個(gè)暴力解法，可以有優(yōu)化一些的算法，就是利用前綴異或和數(shù)組，時(shí)間復(fù)雜度可以減少到 O ( N 2 ) O(N^2) O(N2)，思路如下

第一步

申請(qǐng)一個(gè)和原始數(shù)組一樣長的前綴異或和數(shù)組

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

其中eor[i]表示原始數(shù)組 0 位置到 i 位置的異或和是多少，實(shí)現(xiàn)代碼如下：

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

有了 eor 數(shù)組以后，對(duì)于任意 i 位置，0 到 i 區(qū)間的異或和就可以直接獲取到了，接下來是枚舉數(shù)組中任意兩個(gè)位置 i 和 j 區(qū)間的異或和，由于

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

任何兩個(gè)位置之間的異或和信息可以通過如下代碼求得，其中 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;
  }

整個(gè)算法復(fù)雜度是 O ( N 2 ) O(N^2) O(N2)，并不是最優(yōu)解。

最優(yōu)解

根據(jù)上述暴力解法，時(shí)間復(fù)雜度比較高的部分是：

當(dāng)確定了 0 ~ i 位置的異或和以后，如何定位 0 ~ j 這個(gè)區(qū)間，使得 j ~ i 之間的異或和大。

暴力解法使用的是遍歷的方式，而最優(yōu)解，可以使用前綴樹進(jìn)行加速匹配，關(guān)于前綴樹的內(nèi)容，可以參考：前綴樹的設(shè)計(jì)和實(shí)現(xiàn)

以數(shù)組[11,1,15,10,13,4]為例，我們把其前綴異或和數(shù)組轉(zhuǎn)換成二進(jìn)制，結(jié)果如下(其中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

把這些前綴異或和加入前綴樹,

接下來，對(duì)于任何一個(gè)eor[i](0~i的異或和)來說，進(jìn)入前綴樹以后，前綴樹需要快速找到和其匹配的eor[j]，使得i~j之間的異或和大，規(guī)則就是最高位（符號(hào)位）期待一樣，緊著高位要期待不一樣的值

例如：

eor[2] = 0101

eor[2] 期待和它符號(hào)位一樣為0的值，緊著高位（由于前面28都是0，所以不存在和它符號(hào)不一樣的，只看最后4位，

通過這個(gè)貪心，就可以在 O ( 1 ) O(1) O(1)時(shí)間復(fù)雜度直接得到結(jié)果。

說明：如果期待遇到 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--) {// 符號(hào)位期待一樣的
        // 非符號(hào)位期待相反的
        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];
  }

整個(gè)算法時(shí)間復(fù)雜度 O ( N ) O(N) O(N)，最優(yōu)解。

更多

算法和數(shù)據(jù)結(jié)構(gòu)筆記

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

當(dāng)前題目：子數(shù)組的最大異或和問題-創(chuàng)新互聯(lián)
地址分享：http://www.rwnh.cn/article22/cegdjc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供移動(dòng)網(wǎng)站建設(shè)、電子商務(wù)、App開發(fā)、網(wǎng)站維護(hù)、網(wǎng)站排名、網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)