資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學Python程式：查詢矩陣中第k大XOR座標值
假設我們有一個m x n的矩陣和另一個值k。矩陣座標(a, b)的值是所有matrix[i, j]的XOR值，其中i的範圍是(0到a)，j的範圍是(0到b)。我們需要找到矩陣所有座標的第k大值（從1開始計數）。
例如，輸入如下：
| 5 | 2 |
| 1 | 6 |
如果k = 1，則輸出為7，因為座標(0,1)的值是5 XOR 2 = 7，這是最大的值。
為了解決這個問題，我們將遵循以下步驟：
- m := 行數，n := 列數
- 對於i從0到m-1：
- 對於j從0到n-1：
- 如果j不為零，則
- matrix[i, j] := matrix[i, j] XOR matrix[i, j-1]
- 如果j不為零，則
- 對於j從0到n-1：
- seen := 一個新的對映
- count := 0
- 對於i從0到n-1：
- 對於j從0到m-1：
- 如果j不為零，則
- matrix[j, i] := matrix[j, i] XOR matrix[j-1, i]
- seen[matrix[j, i]] = (如果存在則seen[matrix[j, i]] + 1，否則為1)
- count := count + 1
- 如果count > k，則
- min_value := seen中的最小值
- seen[min_value] := seen[min_value] - 1
- 如果seen[min_value]為0，則
- 從seen中刪除min_value對應的元素
- 如果j不為零，則
- 對於j從0到m-1：
- 返回seen中的最小值
示例
讓我們看看下面的實現以更好地理解：
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
更新於：2021年10月7日
瀏覽量：130
廣告