Last active
May 5, 2019 10:55
-
-
Save LostInKadath/e0670a28a774596d271b1afee6138eaf to your computer and use it in GitHub Desktop.
Найти элемент в отсортированной матрице
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <algorithm> | |
#include <cassert> | |
#include <iostream> | |
#include <memory> | |
template <typename T> | |
class Matrix | |
{ | |
public: | |
Matrix(size_t rows, size_t cols, T value) | |
: m_rows(rows) | |
, m_cols(cols) | |
, m_data(new T[rows * cols]) | |
{ | |
for (size_t row = 0; row < rows; ++row) | |
for (size_t col = 0; col < cols; ++col) | |
*(m_data.get() + row * cols + col) = value; | |
} | |
Matrix(std::initializer_list<std::initializer_list<T>> args) | |
{ | |
m_rows = args.size(); | |
m_cols = args.begin()->size(); | |
m_data.reset(new T[m_rows * m_cols]); | |
auto inner = args.begin(); | |
for (size_t row = 0; row < m_rows; ++row, ++inner) | |
std::copy(std::begin(*inner), std::end(*inner), m_data.get() + row * m_cols); | |
} | |
T operator()(size_t row, size_t col) const | |
{ | |
if (row < 0 || row >= m_rows) | |
throw std::invalid_argument("invalid row index"); | |
if (col < 0 || col >= m_cols) | |
throw std::invalid_argument("invalid column index"); | |
return *(m_data.get() + row * m_cols + col); | |
} | |
T& operator()(size_t row, size_t col) | |
{ | |
if (row < 0 || row >= m_rows) | |
throw std::invalid_argument("invalid row index"); | |
if (col < 0 || col >= m_cols) | |
throw std::invalid_argument("invalid column index"); | |
return *(m_data.get() + row * m_cols + col); | |
} | |
size_t rows() const { return m_rows; } | |
size_t cols() const { return m_cols; } | |
template <typename U> | |
friend std::ostream& operator<<(std::ostream& os, const Matrix<U>& matrix); | |
private: | |
std::unique_ptr<T> m_data = nullptr; | |
size_t m_rows = 0; | |
size_t m_cols = 0; | |
}; | |
template <typename T> | |
inline std::ostream& operator<<(std::ostream& os, const Matrix<T>& matrix) | |
{ | |
for (size_t row = 0; row < matrix.m_rows; ++row) | |
{ | |
for (size_t col = 0; col < matrix.m_cols; ++col) | |
os << *(matrix.m_data.get() + row * matrix.m_cols + col) << ' '; | |
os << '\n'; | |
} | |
return os; | |
} | |
std::pair<int, int> Task70(const Matrix<int>& matrix, int value) | |
{ | |
int row = 0; | |
int col = static_cast<int>(matrix.cols() - 1); | |
while (col >= 0 && row < matrix.rows()) | |
{ | |
const auto current = matrix(row, col); | |
if (current == value) | |
return std::make_pair(row, col); | |
else if (current > value) | |
--col; | |
else | |
++row; | |
} | |
return std::make_pair(-1, -1); | |
} | |
int main() | |
{ | |
Matrix<int> matrix({ | |
{ 1, 5, 10, 20}, | |
{ 7, 9, 15, 28}, | |
{12, 25, 30, 36}, | |
{22, 35, 45, 50} | |
}); | |
auto answer = Task70(matrix, 45); | |
assert(answer.first == 3 && answer.second == 2); | |
answer = Task70(matrix, 44); | |
assert(answer.first == -1 && answer.second == -1); | |
system("pause"); | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Задача 70: | |
Найти элемент в отсортированной матрице (матрица, в которой строки и столбцы отсортированы). | |
Если такого элемента нет, вывести сообщение об ошибке. | |
Ход решения: | |
Начнем с верхнего правого угла матрицы и будем двигаться по элементам, используя следующую логику: | |
1. Если элемент, на котором мы стоим, равен искомому элементу, возвращаем индексы строки и столбца; | |
2. Если элемент больше заданного, нам нужно идти в сторону уменьшения - то есть налево по строке; | |
3. Если элемент меньше заданного, нам нужно идти в сторону увеличения - то есть вниз по столбцу. | |
Пункты 2-3 справедливы вследствие сортированности строк и столбцов матрицы. | |
Если при поиске мы вылетели за границы матрицы, значит, матрица не содержит данного элемента. | |
Сложность алгоритма в худшем случае: O(n+m), где n,m - размерности матрицы. | |
PS. В ходе решения задачи был написан собственный класс матрицы, реализующий исключительно ту функциональность, которая нужна в рамках этой задачи. Как говорится, любой программист должен, прежде всего, написать свои классы вектора и матрицы. =) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment