Golang вопросы собеседований

📌 Задача с Leetcode. Поиск в двумерной матрице

Сложность: Средняя

Условие задачи: напишите эффективный алгоритм для поиска наличия нужного числа в двумерной матрице, которая имеет следующие свойства:

▪ в строке элементы отсортированы по возрастанию (слева - направо);
▪ в столбце элементы отсортированы по возрастанию (снизу - вверх).

Пример:

Ввод: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Вывод: true

Решение:

func searchMatrix(matrix [][]int, target int) bool {
m, n := len(matrix), len(matrix[0])
i, j := 0, n-1
for i < m && j >= 0 {
if matrix[i][j] == target {
return true
}
if matrix[i][j] < target {
i++
} else {
j--
}
}
return false
}


Временная сложность: O(m + n)
Пространственная сложность: O(1)


Пишите свое решение в комментариях👇

@golang_interview

❤5🤡2👍1🔥1

www.tgoop.com/golang_interview/182

2.88K viewsedited  Apr 27, 2023 at 16:11

📌 Задача с Leetcode. Поиск в двумерной матрице

Сложность: Средняя

Условие задачи: напишите эффективный алгоритм для поиска наличия нужного числа в двумерной матрице, которая имеет следующие свойства:

▪ в строке элементы отсортированы по возрастанию (слева - направо);
▪ в столбце элементы отсортированы по возрастанию (снизу - вверх).

Пример:

Ввод: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Вывод: true

Решение:

func searchMatrix(matrix [][]int, target int) bool {
m, n := len(matrix), len(matrix[0])
i, j := 0, n-1
for i < m && j >= 0 {
if matrix[i][j] == target {
return true
}
if matrix[i][j] < target {
i++
} else {
j--
}
}
return false
}


Временная сложность: O(m + n)
Пространственная сложность: O(1)


Пишите свое решение в комментариях👇

@golang_interview

BY Golang вопросы собеседований