Python에서 k 번째로 큰 XOR 좌표 값을 찾는 프로그램

<시간/>

하나의 m x n 행렬이 있다고 가정합니다. 및 또 다른 값 k. 여기서 행렬의 좌표(a, b) 값은 모든 행렬[i, j]의 XOR입니다. 여기서 i는 범위(0~a)이고 j는 범위(0~b)입니다. 행렬의 모든 좌표 중 k번째로 큰 값(1-indexed)을 찾아야 합니다.

따라서 입력이 다음과 같으면

5	2
1	6

그리고 k =1이면 좌표 (0,1)의 값이 5 XOR 2 =7이고 이것이 가장 큰 값이기 때문에 출력은 7이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

m :=행 개수, n :=열 개수
0 ~ m - 1 범위의 i에 대해
- 0 ~ n - 1 범위의 j에 대해 다음을 수행합니다.
  - j가 0이 아니면
    - 행렬[i, j] :=행렬[i, j] XOR 행렬[i, j-1]
본 :=새 지도
카운트:=0
0 ~ n - 1 범위의 i에 대해
- 0 ~ m - 1 범위의 j에 대해
  - j가 0이 아니면
    - 행렬[j, i] :=행렬[j, i] XOR 행렬[j-1, i]
  - seen[matrix[j, i]] =(1+seen[matrix[j, i]] 가능하면 1)
  - 카운트 :=카운트 + 1
  - 만약 count> k이면
    - min_value :=본 것 중 최소값
    - 본[최소값] :=본[최소값] - 1
    - 본[최소값]이 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