Сложность: medium
Дана матрица mat размером m x n, где каждая строка отсортирована в строго возрастающем порядке. Верните наименьший общий элемент во всех строках.
Если общего элемента нет, верните -1.
Пример:
Input: mat = [[1,2,3,4,5],[2,4,5,8,10],[3,5,7,9,11],[1,3,5,7,9]]
Output: 5
👨💻 Алгоритм:
1⃣Инициализация переменных:
Инициализируйте массив позиций pos, переменную для текущего максимального значения cur_max и счетчик cnt нулями.
2⃣Итерация по строкам матрицы:
Для каждой строки:
- увеличивайте позицию в строке, пока значение не станет равным или больше текущего максимума.
- если достигли конца строки, возвращайте -1.
- если значение равно текущему максимуму, увеличивайте счетчик.
- в противном случае, сбросьте счетчик до 1 и обновите текущий максимум.
3⃣Проверка счетчика:
Если счетчик равен количеству строк, возвращайте текущий максимум.
Повторите шаг 2.
😎 Решение:
class Solution:
def smallestCommonElement(self, mat: List[List[int]]) -> int:
n = len(mat)
m = len(mat[0])
pos = [0] * n
cur_max = 0
cnt = 0
while True:
for i in range(n):
while pos[i] < m and mat[i][pos[i]] < cur_max:
pos[i] += 1
if pos[i] >= m:
return -1
if mat[i][pos[i]] != cur_max:
cnt = 1
cur_max = mat[i][pos[i]]
else:
cnt += 1
if cnt == n:
return cur_max
Ставь 👍 и забирай 📚 Базу знаний