Hai phần tử trong mảng có xor là tối đa

Question

Cho một mảng các số nguyên, Bạn phải tìm hai phần tử có XOR là lớn nhất.

Có cách tiếp cận ngây thơ - bằng cách chọn từng phần tử và xoring với các phần tử khác và sau đó so sánh kết quả để tìm cặp.

Khác với điều này, Có bất kỳ thuật toán hiệu quả nào không?

Answer 1

Tôi nghĩ rằng tôi có một thuật toán O (n lg U) cho điều này, trong đó U là số lớn nhất. Ý tưởng này tương tự như của user949300, nhưng với một chút chi tiết hơn.

Trực giác như sau.Khi bạn XORing hai số với nhau, để có được giá trị tối đa, bạn muốn có 1 ở vị trí cao nhất có thể, và sau đó của các cặp có 1 ở vị trí này, bạn muốn ghép đôi với 1 ở vị trí tiếp theo vị trí cao nhất có thể, v.v.

Vì vậy, thuật toán như sau. Bắt đầu bằng cách tìm 1 bit cao nhất ở bất kỳ đâu trong các con số (bạn có thể làm điều này trong thời gian O (n lg U) bằng cách thực hiện công việc O (lg U) cho mỗi số n). Bây giờ, chia mảng thành hai phần - một trong những số có 1 trong bit đó và nhóm có 0 trong bit đó. Bất kỳ giải pháp tối ưu nào cũng phải kết hợp một số với số 1 ở vị trí đầu tiên với một số có 0 ở vị trí đó, vì điều đó sẽ đặt một bit cao nhất có thể. Bất kỳ cặp đôi nào khác có 0 ở đó.

Bây giờ, đệ quy, chúng tôi muốn tìm ghép các số từ nhóm 1 và 0 có số cao nhất trong số đó. Để làm điều này, trong hai nhóm này, chia chúng thành bốn nhóm:

• số bắt đầu với 11
• số bắt đầu với 10
• số bắt đầu với 01
• số bắt đầu với 00

Nếu có bất kỳ số nào trong nhóm 11 và 00 hoặc trong 10 và 01 nhóm, XOR của chúng sẽ là lý tưởng (bắt đầu bằng 11). Do đó, nếu một trong hai cặp nhóm đó không có sản phẩm nào, hãy tính toán giải pháp lý tưởng một cách đệ quy từ các nhóm đó, sau đó trả về tối đa các giải pháp dưới đây. Nếu không, nếu cả hai nhóm trống, điều này có nghĩa là tất cả các số phải có cùng chữ số ở vị trí thứ hai của chúng. Do đó, XOR tối ưu của một số bắt đầu bằng 1 và một số bắt đầu bằng 0 sẽ kết thúc có bit thứ hai tiếp theo bị hủy, vì vậy chúng ta chỉ cần nhìn vào bit thứ ba.

Điều này cho phép các thuật toán đệ quy sau đó, bắt đầu với hai nhóm số phân chia bởi MSB của họ, cung cấp cho câu trả lời:

• Với nhóm 1 và nhóm 0 và một chỉ số chút i:
  • Nếu chỉ số bit bằng số bit, trả về XOR của số (duy nhất) trong nhóm 1 và số (duy nhất) trong nhóm 0.
  • Tạo nhóm 11, 10, 01 và 00 từ các nhóm đó.
  • Nếu nhóm 11 và nhóm 00 không có giá trị, đệ quy tìm XOR tối đa của hai nhóm đó bắt đầu từ bit i + 1.
  • . bắt đầu từ bit i + 1.
  • Nếu một trong các cặp trên có thể xảy ra, sau đó trả lại cặp tối đa do đệ quy tìm thấy.
  • Nếu không, tất cả các con số phải có chút tương tự ở vị trí i, nên trả lại cặp tối đa tìm thấy bằng cách nhìn vào chút i + 1 vào nhóm 1 và 0.

Để bắt đầu ra khỏi thuật toán, bạn thực sự có thể phân vùng các số từ nhóm ban đầu thành hai nhóm - các số có MSB 1 và các số có MSB 0. Sau đó bạn sẽ thực hiện cuộc gọi đệ quy đến thuật toán trên với hai nhóm số.

Ví dụ, hãy xem xét các số 5 1 4 3 0 2.Những có cơ quan đại diện

101 001 100 011 000 010 

Chúng tôi bắt đầu bằng cách tách chúng thành 1 nhóm và nhóm 0:

101 100 
001 011 000 010 

Bây giờ, chúng tôi áp dụng các thuật toán ở trên. Chúng tôi chia nhóm này thành các nhóm 11, 10, 01 và 00:

11: 
10: 101 100 
01: 011 010 
00: 000 001 

Bây giờ, chúng tôi không thể ghép nối bất kỳ 11 phần tử với 00 yếu tố, vì vậy chúng tôi chỉ recurse trên 10 và 01 nhóm. Điều này có nghĩa là chúng tôi xây dựng các nhóm 100, 101, 010 và 011:

101: 101 
100: 100 
011: 011 
010: 010 

Bây giờ, chúng tôi chỉ cần kiểm tra các cặp 101 và 010 (cung cấp 111) và 100 và 011 (cho 111). Hoặc tùy chọn hoạt động ở đây, vì vậy chúng tôi nhận được câu trả lời tối ưu là 7.

Hãy suy nghĩ về thời gian chạy của thuật toán này. Lưu ý rằng độ sâu đệ quy tối đa là O (lg U), vì chỉ có các bit O (log U) trong các số. Ở mỗi cấp trong cây, mỗi số xuất hiện chính xác trong một cuộc gọi đệ quy, và mỗi cuộc gọi đệ quy làm việc tỷ lệ thuận với tổng số các số trong nhóm 0 và 1, bởi vì chúng ta cần phân phối chúng theo bit của chúng. Do đó, có O (log U) cấp trong cây đệ quy, và mỗi cấp độ O (n) làm việc, cho một tổng công việc của O (n log U).

Hy vọng điều này sẽ hữu ích! Đây là một vấn đề tuyệt vời!

Answer 2

Bỏ qua bit dấu, một trong các giá trị phải là một trong các giá trị có bộ bit quan trọng cao nhất. Trừ khi tất cả các giá trị có bit được đặt là, trong trường hợp này, bạn chuyển đến bit quan trọng cao nhất tiếp theo không được đặt trong tất cả các giá trị. Vì vậy, bạn có thể pare xuống khả năng cho giá trị 1 bằng cách nhìn vào HSB. Ví dụ: nếu khả năng là

0x100000 
0x100ABC 
0x001ABC 
0x000ABC 

Giá trị thứ nhất của cặp tối đa phải là 0x100000 hoặc 0x10ABCD.

@internal Lỗi máy chủ Tôi không cho là nhỏ nhất là đúng. Tôi không có ý tưởng tuyệt vời cho việc giảm giá trị thứ 2. Chỉ bất kỳ giá trị nào mà không phải là trong danh sách giá trị 1 có thể có. Trong ví dụ của tôi, 0x001ABC hoặc 0x000ABC.

Answer 3

Thực hiện chức năng đệ quy lấy hai danh sách các số nguyên, A và B, làm đối số của nó. Là giá trị trả về của nó, nó trả về hai số nguyên, một từ A và một từ B, giúp tối đa hóa XOR của hai số nguyên. Nếu tất cả các số nguyên là 0, trả về (0,0). Nếu không, hàm sẽ thực hiện một số xử lý và gọi chính nó đệ quy hai lần, nhưng với các số nguyên nhỏ hơn. Trong một trong các cuộc gọi đệ quy, nó xem xét lấy một số nguyên từ danh sách A để cung cấp 1 đến bit k, và trong cuộc gọi khác nó xem xét lấy một số nguyên từ danh sách B để cung cấp một bit 1 đến bit k.

Tôi không có thời gian để điền chi tiết, nhưng có lẽ điều này sẽ đủ để xem câu trả lời? Ngoài ra, tôi không chắc chắn nếu thời gian chạy sẽ tốt hơn N^2, nhưng nó có thể sẽ được.

Answer 4

Một vấn đề rất thú vị! Đây là ý tưởng của tôi:

• đầu tiên xây dựng một cây nhị phân từ tất cả các số bằng nhị phân đại diện và sắp xếp chúng vào cây bit quan trọng nhất đầu tiên (thêm số không hàng đầu để phù hợp với số dài nhất). Khi thực hiện mỗi đường dẫn từ gốc đến bất kỳ lá nào đại diện cho một số từ tập hợp gốc.
• Để a và b là con trỏ đến nút cây và khởi tạo chúng ở gốc.
• Bây giờ di chuyển a và b xuống cây, cố gắng sử dụng các cạnh đối diện ở mỗi bước, tức là nếu di chuyển xuống 0 cạnh, b di chuyển xuống 1 cạnh trừ khi không thể.

Nếu a và b đến một lá, nên trỏ đến hai số có bit giống hệt nhau "rất ít".

Tôi chỉ thực hiện thuật toán này và không biết chính xác hay cách chứng minh nó. Tuy nhiên nó phải ở trong thời gian chạy O (n).

Answer 5

Chúng tôi có thể tìm số lượng tối đa trong khoảng thời gian O (n) rồi lặp qua mảng làm xor với từng phần tử. Giả sử chi phí hoạt động xor là O (1), chúng ta có thể tìm thấy xor tối đa của hai số trong thời gian O (n).

Answer 6

Điều này có thể được giải quyết trong O(NlogN) độ phức tạp về thời gian sử dụng Trie.

• Xây dựng bộ ba. Đối với mỗi phím số nguyên, mỗi nút của trie sẽ giữ mọi bit (0 hoặc 1) bắt đầu từ bit quan trọng nhất.
• Bây giờ cho mỗi phần tử arr[i] của arr[0, 1, ..... N]
  • Thực hiện truy vấn để lấy giá trị xor tối đa có thể cho arr[i]. Chúng tôi biết xor của các loại bit khác nhau (0^1 hoặc 1^0) luôn là 1. Vì vậy, trong quá trình truy vấn cho từng bit, hãy thử duyệt qua nút giữ bit đối diện. Điều này sẽ làm cho kết quả bit cụ thể đó là 1 tối đa hóa giá trị xor. Nếu không có nút nào có bit đối diện, chỉ sau đó đi qua cùng một nút bit.
  • Sau khi truy vấn, hãy chèn arr[i] vào trie.
  • Đối với mỗi thành phần, hãy theo dõi giá trị Xor tối đa có thể.
  • Trong khi đi qua từng nút, hãy tạo khóa khác mà Xor đang được phóng to.

Đối N yếu tố, chúng ta cần một truy vấn (O(logN)) và một chèn (O(logN)) cho mỗi yếu tố. Vì vậy, tổng thời gian phức tạp là O(NlogN).

Bạn có thể tìm thấy giải thích bằng hình ảnh đẹp về cách hoạt động in this thread.

Dưới đây là C++ thực hiện của thuật toán trên:

const static int SIZE = 2; 
const static int MSB = 30; 
class trie { 
private: 
    struct trieNode { 
     trieNode* children[SIZE]; 
     trieNode() { 
      for(int i = 0; i < SIZE; ++i) { 
       children[i] = nullptr; 
      } 
     } 
     ~trieNode() { 
      for(int i = 0; i < SIZE; ++i) { 
       delete children[i]; 
       children[i] = nullptr; 
      } 
     } 
    }; 
    trieNode* root; 
public: 
    trie(): root(new trieNode()) { 
    } 
    ~trie() { 
     delete root; 
     root = nullptr; 
    } 

    void insert(int key) { 
     trieNode* pCrawl = root; 
     for(int i = MSB; i >= 0; --i) { 
      bool bit = (bool)(key & (1 << i)); 
      if(!pCrawl->children[bit]) { 
       pCrawl->children[bit] = new trieNode(); 
      } 
      pCrawl = pCrawl->children[bit]; 
     } 
    } 

    int query(int key, int& otherKey) { 
     int Xor = 0; 
     trieNode *pCrawl = root; 
     for(int i = MSB; i >= 0; --i) { 
      bool bit = (bool)(key & (1 << i)); 
      if(pCrawl->children[!bit]) { 
       pCrawl = pCrawl->children[!bit]; 
       Xor |= (1 << i); 
       if(!bit) { 
        otherKey |= (1 << i); 
       } else { 
        otherKey &= ~(1 << i); 
       } 
      } else { 
       if(bit) { 
        otherKey |= (1 << i); 
       } else { 
        otherKey &= ~(1 << i); 
       } 
       pCrawl = pCrawl->children[bit]; 
      } 
     } 
     return Xor; 
    } 
}; 

pair<int, int> findMaximumXorElements(vector<int>& arr) { 
    int n = arr.size(); 
    int maxXor = 0; 
    pair<int, int> result; 
    if(n < 2) return result; 
    trie* Trie = new trie(); 
    Trie->insert(0); // insert 0 initially otherwise first query won't find node to traverse 
    for(int i = 0; i < n; i++) { 
     int elem = 0; 
     int curr = Trie->query(arr[i], elem); 
     if(curr > maxXor) { 
      maxXor = curr; 
      result = {arr[i], elem}; 
     } 
     Trie->insert(arr[i]); 
    } 
    delete Trie; 
    return result; 
}