Самый эффективный способ поиска отсортированной матрицы?

Question

У меня есть задание написать алгоритм (не на каком-то конкретном языке, просто псевдокод), который получает матрицу [размер: M x N], которая сортируется таким образом, что все ее строки сортируются и всеего столбцы сортируются по отдельности и находят определенное значение в этой матрице.Мне нужно написать наиболее эффективный по времени алгоритм, который я только могу придумать.

Матрица выглядит примерно так:

1  3  5
4  6  8
7  9 10

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

Answer 1

Ваша матрица выглядит так:

a ..... b ..... c
. .     . .     .
.   1   .   2   . 
.     . .     . .
d ..... e ..... f
. .     . .     .
.   3   .   4   .
.     . .     . .
g ..... h ..... i

и имеет следующие свойства:

a,c,g < i  
a,b,d < e
b,c,e < f
d,e,g < h
e,f,h < i

Таким образом, значение в самом нижнем углу (например, i) всегда самое большое во всей матрице и это свойство является рекурсивным, если разделить матрицу на 4 равные части.

Итак, мы можем попытаться использовать бинарный поиск:

1. зонд для значения,
2. разделить на части,
3. выбрать правильный кусок (каким-то образом),
4. Перейти к 1 с новым куском.

Следовательно, алгоритм может выглядеть так:

input: X - value to be searched
until found
 divide matrix into 4 equal pieces
 get e,f,h,i as shown on picture
 if (e or f or h or i) equals X then 
   return found
 if X < e then quarter := 1
 if X < f then quarter := 2
 if X < h then quarter := 3
 if X < i then quarter := 4
 if no quarter assigned then 
    return not_found
 make smaller matrix from chosen quarter 

Это выглядит как O (log n), где n - количество элементов в матрице. Это своего рода бинарный поиск, но в двух измерениях. Я не могу доказать это формально, но напоминает типичный бинарный поиск.

Answer 2

в журнале M вы можете получить диапазон строк, которые могут содержать цель (бинарный поиск по первому значению строк, бинарный поиск по последнему значению строк, сохранить только те строки, у которых first <= target и last> = target ) два двоичных поиска по-прежнему O (log M)
затем в O (log N) вы можете исследовать каждую из этих строк, снова используя бинарный поиск!

что делает его O (logM x logN) * ​​1004 * tadaaaa

Answer 3

а вот так выглядит пример ввода?Сортировать по диагонали?Это интересный вид, чтобы быть уверенным.

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

Я бы (если бы попросили сделать это на большом входе) прочитал бы матрицу в структуру списка, в которой данные были взяты в виде одной пары кортежа, а координата mxn - в качестве части кортежа, изатем быстро сортируйте матрицу один раз, затем найдите ее по значению.

В качестве альтернативы, если значение каждого отдельного местоположения уникально, сбросьте данные MxN в словарь с ключом значения, затем перейдите к словарной записи MxN на основе ключа ввода (или хеша).ключа ввода).

РЕДАКТИРОВАТЬ:

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

for (int i = 0; i<M; i++)
 for (int j=0; j<N; j++)
  if (mat[i][j] == value) return tuple(i,j);

---

Очевидно, мой комментарий по этому вопросу также должен быть здесь: |

@ Сагар, но это не тот пример, который дал профессор.в противном случае у него был самый быстрый метод, описанный выше (сначала проверьте конец строки, затем продолжите). Кроме того, сначала быстрее проверяется конец середины строки, что немного похоже на двоичный поиск.

Проверкаконец каждой строки (и начинающийся в конце средней строки), чтобы найти число выше, чем проверенное число в массиве в памяти, был бы самым быстрым, затем выполнял бы бинарный поиск по каждой соответствующей строке, пока вы не найдете его.

Answer 4

Решение JavaScript:

//start from the top right corner
//if value = el, element is found
//if value < el, move to the next row, element can't be in that row since row is sorted
//if value > el, move to the previous column, element can't be in that column since column is sorted

function find(matrix, el) {

  //some error checking
  if (!matrix[0] || !matrix[0].length){
    return false;
  }
  if (!el || isNaN(el)){
    return false;
  }

  var row = 0; //first row
  var col = matrix[0].length - 1; //last column

  while (row < matrix.length && col >= 0) {
    if (matrix[row][col] === el) { //element is found
      return true;
    } else if (matrix[row][col] < el) {
      row++; //move to the next row
    } else {
      col--; //move to the previous column
    }
  }

  return false;

}

Answer 5

Это в духе Ответ Михала (из которого я украду красивую графику).

Матрица:

  min ..... b ..... c
    .       .       .
    .  II   .   I   . 
    .       .       .
    d .... mid .... f
    .       .       .
    .  III  .   IV  .
    .       .       .
    g ..... h ..... max

Мин. И макс.наименьшее и наибольшее значения соответственно."mid" не обязательно означает среднее / медиану / любое другое значение.

Мы знаем, что значение в середине равно> = всем значениям в квадранте II и <= всем значениям в квадранте IV.Мы не можем предъявлять такие требования к квадрантам I и III.Если мы вернемся, мы можем исключить один квадрант на каждом уровне. </p>

Таким образом, если целевое значение меньше среднего, мы должны искать квадранты I, II и III.Если целевое значение больше среднего, мы должны искать квадранты I, III и IV.

На каждом шаге пространство уменьшается до 3/4 по сравнению с предыдущим:

n * (3 /4) ^x = 1

n = (4/3) ^x

x = log _4/3 (n)

Логарифмы отличаются постоянным коэффициентом, поэтому это O (log (n)).

find(min, max, target)
    if min is max
        if target == min
            return min
        else
            return not found
    else if target < min or target > max
        return not found
    else
        set mid to average of min and max 
        if target == mid
            return mid
        else
            find(b, f, target), return if found
            find(d, h, target), return if found

            if target < mid
                return find(min, mid, target)
            else
                return find(mid, max, target)

Answer 6

Здесь нижняя граница n . Начните с несортированного массива A длиной n . Создайте новую матрицу M по следующему правилу: вторичная диагональ содержит массив A, все, что выше, - минус бесконечность, все, что ниже, - плюс бесконечность. Строки и столбцы сортируются, и поиск записи в M аналогичен поиску записи в A.

Answer 7

как насчет вывода диагонали, затем двоичного поиска по диагонали, запускаем нижнюю правую проверку, если она выше, если да, выбираем позицию диагонального массива в качестве столбца, в котором он находится, если нет, то проверяем, находится ли он ниже.каждый раз, выполняя бинарный поиск по столбцу, когда вы нажимаете на диагональ (используя позицию массива диагонали в качестве индекса столбца).Я думаю, что это то, что было сказано @ user942640

, вы можете получить время выполнения вышеприведенного и при необходимости (в какой-то момент) поменять местами алгоритм, чтобы выполнить двоичный поиск по исходному диагональному массиву (это занимаетпринимая во внимание, что его n * n элементов и получение длины x или y равно O (1) как x.length = y.length, даже при бинарном поиске миллиона * миллионов по диагонали, если она меньше половины шага назад по диагонали, еслиэто не меньше, чем бинарный поиск обратно туда, где вы находитесь (это небольшое изменение алгоритма при выполнении бинарного поиска по диагонали). Я думаю, что диагональ лучше, чем бинарный поиск по строкам, я просто усталмомент, чтобы взглянуть на математику:)

, кстати, я считаю, что время выполнения немного отличается от анализа, который вы бы описали в терминах лучший / худший / средний случай, и время в зависимости от объема памяти и т. д., поэтомувопрос лучше сформулировать так: «каково лучшее время выполнения при анализе наихудшего случая», потому что в лучшем случае вы могли бывыполнить грубое линейное сканирование, и элемент может оказаться на первой позиции, и это будет лучшим «временем выполнения», чем двоичный поиск ...

Answer 8

это неправильный ответ

Я действительно не уверен, являются ли какие-либо ответы оптимальными. Я иду на это.

1. бинарный поиск по первой строке и первому столбцу и выяснение строки и столбца, где может быть "x". вы получите 0, J и I, 0. x будет в строке i или столбце j, если x не найден на этом шаге.
2. двоичный поиск по строке i и столбцу j, найденному на шаге 1.

Мне кажется, сложность по времени составляет 2 * (log m + log n).

Вы можете уменьшить константу, если входной массив представляет собой квадрат (n * n), путем двоичного поиска по диагонали.

Answer 9

public static boolean find(int a[][],int rows,int cols,int x){
    int m=0;
    int n=cols-1;
while(m<rows&&n>=0){
    if(a[m][n]==x)
        return1;
    else if(a[m][n]>x)
        n--;
    else m++;
}

}