โปรแกรมค้นหาค่าพิกัด XOR ที่ใหญ่ที่สุดลำดับที่ k ใน Python

สมมติว่าเรามีเมทริกซ์ขนาด m x n หนึ่งตัว และอีกค่า k ที่นี่ค่าของพิกัด (a, b) ของเมทริกซ์คือ XOR ของเมทริกซ์ทั้งหมด[i, j] โดยที่ i อยู่ในช่วง (0 ถึง a) และ j ในช่วง (0 ถึง b) เราต้องหาค่าที่มากที่สุดเป็นอันดับที่ k (จัดทำดัชนี 1 รายการ) ของพิกัดทั้งหมดของเมทริกซ์

ดังนั้นหากอินพุตเป็นแบบ

5	2
1	6

และ k =1 ผลลัพธ์จะเป็น 7 เพราะค่าพิกัด (0,1) คือ 5 XOR 2 =7 และนี่คือค่าที่ใหญ่ที่สุด

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

m :=จำนวนแถว n :=จำนวนคอลัมน์
สำหรับฉันในช่วง 0 ถึง m - 1 ทำ
- สำหรับ j ในช่วง 0 ถึง n - 1 ทำ
  - ถ้า j ไม่ใช่ศูนย์ แล้ว
    - เมทริกซ์[i, j] :=เมทริกซ์[i, j] เมทริกซ์ XOR[i, j-1]
เห็น :=แผนที่ใหม่
นับ :=0
สำหรับฉันในช่วง 0 ถึง n - 1 ทำ
- สำหรับ j ในช่วง 0 ถึง m - 1 ทำ
  - ถ้า j ไม่ใช่ศูนย์ แล้ว
    - เมทริกซ์[j, i] :=เมทริกซ์[j, i] เมทริกซ์ XOR[j-1, i]
  - เห็น[เมทริกซ์[j, i]] =(1+มองเห็น[เมทริกซ์[j, i]] ถ้าเป็นไปได้ มิฉะนั้น 1)
  - นับ :=นับ + 1
  - ถ้านับ> k แล้ว
    - min_value :=เห็นขั้นต่ำ
    - เห็น[min_value] :=เห็น[min_value] - 1
    - ถ้าเห็น[min_value] เป็น 0 แล้ว
      - ลบองค์ประกอบ min_value-th จากที่เห็น
คืนขั้นต่ำที่เห็น

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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