實現一個函數,給定一個矩陣和一個元素,找到該元素在矩陣中的行和列下標。如果矩陣中存在多個相同元素,則返回它們中任意一個的下標即可。
def find_element(matrix, element):
"""
:type matrix: List[List[int]]
:type element: int
:rtype: Tuple[int, int]
"""
if not matrix or not matrix[0]:
return None
m, n = len(matrix), len(matrix[0])
left, right = 0, m * n - 1
while left<= right:
mid = (left + right) // 2
i, j = divmod(mid, n)
if matrix[i][j] == element:
return i, j
elif matrix[i][j]< element:
left = mid + 1
else:
right = mid - 1
return None
這里使用二分查找,在矩陣中查找元素。因為矩陣有序,所以可以使用二分查找來優化查找效率。首先將整個矩陣變成一個有序的一維數組,然后在這個一維數組中進行二分查找。我們將一維數組中的下標映射回二維矩陣中,即可得到元素在矩陣中的行和列下標。
上一篇c json 壓縮
下一篇python 技能樹效果