음수가 아닌 값을 가진 num이라는 배열이 있다고 가정합니다. 또한 쿼리[i]에 쌍(xi, mi)이 있는 쿼리라는 또 다른 배열이 있습니다. i번째 쿼리의 답은 xi의 최대 비트 XOR 값과 mi보다 작거나 같은 num의 모든 요소입니다. nums의 모든 요소가 mi보다 크면 답은 -1입니다. 그래서 우리는 sizeof 답변이 쿼리의 크기와 같고 answer[i]가 i번째 쿼리에 대한 답변인 배열 답변을 찾아야 합니다.
따라서 입력이 nums =[0,1,2,3,4] 쿼리 =[[3,1],[1,3],[5,6]]과 같으면 출력은 [3, 3,7] 때문에
-
0과 1은 1보다 크지 않습니다. 0 XOR 3 =3 및 1 XOR 3 =2, 여기서 이 둘 중 더 큰 값은 3입니다.
-
1 XOR 2 =3.
-
5 XOR 2 =7.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
m :=숫자 크기
-
n :=쿼리 크기
-
쿼리 =각 인덱스 i에 대해 트리플렛(i, x, limit)을 만들고 쿼리에서 쌍(x, limit)을 만듭니다.
-
제한에 따라 쿼리 정렬
-
nums :=목록 숫자 정렬
-
res :=크기가 n이고 0으로 채워지는 배열
-
범위 31에서 0 사이의 k에 대해 1만큼 감소, 수행
-
접두사 :=새로운 세트
-
j :=0
-
쿼리의 각 인덱스 i 및 값(x, 제한)에 대해 수행
-
동안 j <=m - 1 및 nums[j] <=제한, 수행
-
nums[j]를 오른쪽 k 비트로 이동하고 접두사에 삽입
-
j :=j + 1
-
-
접두사가 비어 있으면
-
해상도[i] :=-1
-
-
그렇지 않으면
-
res[i] =res[i]/2의 몫
-
대상 :=res[i] XOR 1
-
(k 비트를 오른쪽으로 이동한 후 x) XOR 대상이 접두사에 있으면
-
res[i] :=대상
-
-
-
-
-
반환 해상도
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다.
def solve(nums, queries): m, n = len(nums), len(queries) queries = sorted(((i, x, limit) for i, (x, limit) in enumerate(queries)), key=lambda x: x[2]) nums = sorted(nums) res = [0] * n for k in range(31, -1, -1): prefixes = set() j = 0 for i, x, limit in queries: while j <= m - 1 and nums[j] <= limit: prefixes.add(nums[j] >> k) j += 1 if not prefixes: res[i] = -1 else: res[i] <<= 1 target = res[i] ^ 1 if (x >> k) ^ target in prefixes: res[i] = target return res nums = [0,1,2,3,4] queries = [[3,1],[1,3],[5,6]] print(solve(nums, queries))
입력
[0,1,2,3,4], [[3,1],[1,3],[5,6]]
출력
[3, 3, 7]