โปรแกรมหาค่า XOR ของพิกัดที่ใหญ่เป็นอันดับ k ใน Python

ได้รับเมทริกซ์ m×n และค่า k ค่าของพิกัด (a,b) คือ XOR ของ matrix[i][j] ทุกคู่ 0<=i<=a, 0<=j<=b ต้องหาค่าที่ใหญ่เป็นอันดับ k (1-indexed) ของทุกพิกัด

ตัวอย่าง: matrix=[[5,2],[1,6]], k=1 ผลลัพธ์ 7 (พิกัด (0,1): 5 XOR 2 = 7)

วิธีแก้ปัญหา

1. คำนวณ prefix XOR แนวนอน แล้วค่อยแนวตั้ง
2. ใช้ dictionary seen เก็บค่าที่พบ
3. รักษาแค่ k ค่ามากที่สุดโดยลบค่าน้อยที่สุดทีละครั้ง

ตัวอย่างโค้ด

def solve(matrix, k):
    m, n = len(matrix), len(matrix[0])
    for i in range(m):
        for j in range(n):
            if j:
                matrix[i][j] ^= matrix[i][j-1]
    seen = {}
    count = 0
    for i in range(n):
        for j in range(m):
            if j:
                matrix[j][i] ^= matrix[j-1][i]
            seen[matrix[j][i]] = seen.get(matrix[j][i], 0) + 1
            count += 1
            if count > k:
                min_value = min(seen)
                seen[min_value] -= 1
                if not seen[min_value]:
                    seen.pop(min_value)
    return min(seen)

matrix = [[5,2],[1,6]]
k = 1
print(solve(matrix, k))

อินพุต

[[5,2],[1,6]], 1

เอาต์พุต

7