Искать в матрице

Постановка проблемы

Нам дан 2D-массив, в котором отсортированы все элементы в любой отдельной строке или столбце. В такой матрице мы должны искать или находить позицию данного ключа. В следующем примере эта проблема более подробно рассматривается.

Подсказка

  • Разделяй и властвуй

Попробуйте сами

  • C ++
  • C++
  • C ++
  • Java
  • Java
  • Python
  • Python
  • JavaScript
  • JavaScript
  • Ruby
  • Ruby
 pair  search_in_matrix (вектор  > matrix, int value) {//TODO: Write - Your - Code return pair  (- 1, -1);} 

Решение

  • C++
  • путь> C ++
  • путь> C ++
  • Java
  • Java
  • Python
  • Python
  • JavaScript
  • JavaScript
  • Ruby
  • Ruby
 pair  search_in_matrix (вектор > матрица, значение int) {int M = matrix.size (); //строки int N = matrix [0] .size (); //столбцы//Начнем поиск сверху справа. //В качестве альтернативы поиск снизу слева//то есть матрица [M-1] [0] также может работать. int i = 0, j = N-1;  while (i  = 0) {if (matrix [i] [j] == value) {return pair  (i, j);  } else if (value  (- 1, -1);} void verify_search (vector > matrix) {for (int i = 0; i  value_loc = search_in_matrix (матрица, матрица [i] [j]);  assert (value_loc.first == i);  assert (value_loc.second == j);  }}} int main (int argc, char const * argv []) {vector > matrix = {{1, 5, 45, 80, 81}, {6, 7, 48, 82, 83}  , {20, 22, 49, 85, 86}, {21, 23, 50, 90, 92}};  verify_search (матрица);  пара  value_loc;  value_loc = search_in_matrix (матрица, 100);  assert (value_loc.first == -1 && value_loc.second == -1);  return 0;} 

Объяснение решения

Сложность выполнения

Линейный, O (m + n), где m — количество строк, а n — количество столбцов.

Сложность памяти

Константа, O (1).

Анализ решения

Одно простое решение — сканировать весь 2D-массив для ключа за время O (мин). Однако есть лучшие решения с меньшей временной сложностью, в которых используется свойство сортировки матрицы. Мы можем использовать двоичный поиск в каждой строке, чтобы определить, существует ли ключ в строке или нет. Временная сложность этого решения составляет O (m * log n). Хотя это выглядит неплохо, у нас есть еще лучшее решение.

Вот алгоритм, который мы собираемся использовать. Начинаем с правого верхнего угла матрицы и сравниваем ее значение с ключом. Если они равны, мы нашли положение ключа. Если ключ меньше текущего элемента, мы перемещаемся на одну позицию влево. Если ключ больше текущего элемента, мы перемещаемся на одну позицию вниз.

Причина в том, что матрица отсортирована, перемещение влево приведет к более низким значениям, чем текущее значение, и перемещение вниз приведет к более высоким значениям, чем текущее значение. Мы продолжаем этот процесс до тех пор, пока либо не найдем элемент, либо не выйдем за границу матрицы (что указывает на то, что ключ не существует). Это решение будет посещать не более m + n элементов в матрице, что дает нам временную сложность O (m + n). Также обратите внимание, что мы не можем выполнять нашу процедуру поиска из верхнего левого или нижнего правого угла, поскольку в обоих случаях клавиши по обе стороны от этого угла увеличиваются или уменьшаются соответственно.. Обратите внимание, что мы также можем начать поиск из левого нижнего угла, что приведет к результатам, аналогичным поиску в правом верхнем углу.

Оцените статью
nanomode.ru
Добавить комментарий