สมมติว่าเรามีอาร์เรย์ที่เรียกว่า nums ซึ่งมีค่าไม่เป็นลบ นอกจากนี้เรายังมีอาร์เรย์อื่นที่เรียกว่าการสืบค้นโดยที่การสืบค้น [i] มีคู่ (xi, mi) คำตอบของแบบสอบถาม ith คือค่า XOR ระดับบิตสูงสุดของ xi และองค์ประกอบใดๆ ของ nums ที่น้อยกว่าหรือเท่ากับ mi หากองค์ประกอบทั้งหมดใน nums มากกว่า mi คำตอบคือ -1 ดังนั้นเราจึงต้องหาคำตอบอาร์เรย์โดยที่ขนาดของคำตอบเท่ากับขนาดของข้อความค้นหาและคำตอบ[i] คือคำตอบของข้อความค้นหา ith
ดังนั้น หากอินพุตเป็น 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 โดยที่มากกว่า 2 ตัวนี้คือ 3
-
1 XOR 2 =3.
-
5 XOR 2 =7.
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
m :=ขนาดของ nums
-
n :=ขนาดของข้อความค้นหา
-
แบบสอบถาม =สร้างแฝด (i, x, ขีด จำกัด ) สำหรับแต่ละดัชนี i และคู่ (x, ขีด จำกัด ) ในแบบสอบถาม
-
จัดเรียงคำค้นหาตามขีดจำกัด
-
nums :=เรียงลำดับรายการ nums
-
res :=อาร์เรย์ขนาด n และเติม 0
-
สำหรับ k ในช่วง 31 ถึง 0, ลดลง 1 ทำ
-
คำนำหน้า :=ชุดใหม่
-
เจ :=0
-
สำหรับแต่ละดัชนี i และค่า (x, จำกัด) ในการสืบค้น ให้ทำ
-
ในขณะที่ j <=m - 1 และ nums[j] <=จำกัด ทำ
-
เลื่อน nums[j] ไปทางขวา k bits และใส่คำนำหน้า
-
เจ :=เจ + 1
-
-
หากคำนำหน้าว่างเปล่า
-
res[i] :=-1
-
-
มิฉะนั้น
-
res[i] =ผลหารของ res[i]/2
-
เป้าหมาย :=res[i] XOR 1
-
ถ้า (x หลังจากเลื่อน k บิตไปทางขวา) 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]
