Computer >> Máy Tính >  >> Lập trình >> Python

Chương trình tìm giá trị tọa độ XOR lớn nhất thứ k trong Python

Giả sử chúng ta có một ma trận m x n. và một giá trị khác k. Ở đây giá trị của tọa độ (a, b) của ma trận là XOR của tất cả ma trận [i, j] trong đó i trong phạm vi (0 đến a) và j trong phạm vi (0 đến b). Chúng ta phải tìm giá trị lớn nhất thứ k (được lập chỉ mục 1) của tất cả các tọa độ của ma trận.

Vì vậy, nếu đầu vào giống như

5 2
1 6

Và k =1, thì đầu ra sẽ là 7 vì giá trị của tọa độ (0,1) là 5 XOR 2 =7 và đây là giá trị lớn nhất

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • m:=số hàng, n:=số cột
  • đối với tôi trong phạm vi từ 0 đến m - 1, thực hiện
    • đối với j trong phạm vi từ 0 đến n - 1, thực hiện
      • nếu j khác 0, thì
        • ma trận [i, j]:=matrix [i, j] Ma trận XOR [i, j-1]
  • đã thấy:=một bản đồ mới
  • số lượng:=0
  • đối với tôi trong phạm vi từ 0 đến n - 1, thực hiện
    • đối với j trong phạm vi từ 0 đến m - 1, thực hiện
      • nếu j khác 0, thì
        • matrix [j, i]:=matrix [j, i] XOR matrix [j-1, i]
      • saw [matrix [j, i]] =(1 + saw [matrix [j, i]] nếu có thể, nếu không thì 1)
      • count:=count + 1
      • nếu đếm> k, thì
        • min_value:=tối thiểu được xem
        • đã thấy [min_value]:=đã thấy [min_value] - 1
        • nếu thấy [min_value] là 0, thì
          • xóa phần tử min_value-th để xem
  • trả lại số tiền tối thiểu đã thấy

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn - 

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))

Đầu vào 

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

Đầu ra 

7