Leetcode 9월 Day16

문제

Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231.

Find the maximum result of ai XOR aj, where 0 ≤ i, j < n.

Could you do this in O(n) runtime?

예시
""
입력: [3, 10, 5, 25, 2, 8]

출력: 28

설명: 최대 결과는 5 ^ 25 = 28입니다.
""

접근하다 -
무차별 대입 접근 방식은 모든 쌍을 고려하고 최대 xor로 쌍을 반환하는 것입니다.

ans = float('-inf')
for i in range(len(arr)):
    for j in range(i, len(arr)):
        ans = max(ans, arr[i]^arr[j])
return ans

이 접근법의 시간 복잡도는 O(n^2)이고 공간 복잡도는 O(1)입니다.

어떻게 최적화할 수 있습니까?

우리는 a^b = 1 if a != b 임을 압니다. (a, b가 0 또는 1이라고 가정).
따라서 두 숫자의 xor는 대부분의 위치에서 비트가 다른 경우 최대가 됩니다.
예를 들어 11001 는 00110 인 11111 로 최대 xor를 제공합니다.
따라서 먼저 모든 숫자를 이진 문자열 표현으로 변환합니다. 그런 다음 각 숫자에 대해 반대 비트(가능한 한 가깝게)로 숫자를 찾고 답을 업데이트합니다.

이제 반대 비트를 가진 숫자를 찾기 위해 시도를 사용할 것입니다. trie에서 검색하는 시간은 O(len(word))입니다.

해결책

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        bin_list = ["{0:b}".format(el) for el in nums]
        max_len = len(max(bin_list, key = lambda x: len(x)))
        bin_list = ["0"*(max_len - len(el)) + el for el in bin_list]
        ans = float('-inf')
        # create a trie and for each representation try to find the exact opposite as much as possible
        trie = {}
        for word in bin_list:
            parent = trie
            for char in (word):
                if char in parent:
                    parent = parent[char]
                else:
                    parent[char] = {}
                    parent = parent[char]
        # now for each item in binary_list, try to find the opposite
        ans = float('-inf')
        for word in bin_list:
            parent = trie
            curr = ''
            for idx, char in enumerate(word):
                to_find = '1' if char == '0' else '0'
                if to_find in parent:
                    curr += to_find
                    parent = parent[to_find]
                else:
                    curr += char
                    parent = parent[char]
                if idx == len(word) - 1:
                    ans = max(ans, int(word, 2) ^ int(curr, 2) )
        return ans  

시간 복잡도 -
바이너리 리스트 생성용 = O(n*log(len_of_digits)) = O(n)
각 단어에 대해 trie = O(n*log(len_of_digits)) = O(n)에서 검색합니다.
따라서 이 솔루션의 시간 복잡도는 대략 O(n)입니다.