Вопрос по performance, algorithm – Найти число в отсортированной матрице (строки n столбцов) в O (log n) [дубликаты]

40

This question already has an answer here:

How do I search for a number in a 2d array sorted left to right and top to bottom? 19 answers

Скажи у меня матрица (MxN), в котором отсортированы строки и столбцы.

All the elements in each row are arranged in increasing order All the elements in each column are arranged in increasing order All the elements are integers

No other assumptions can be made

Example:

[1 5 8 20]

[2 9 19 21]

[12 15 25 30]

Я должен найти, присутствует ли данное число в матрице или нет (Основной поиск). У меня есть алгоритм, который работаетO(n)

int row = 0;
int col = N-1;

while (row < M && col >= 0) {
  if (mat[row][col] == elem) { 
    return true;
  } else if (mat[row][col] > elem) { 
    col--;
  } else { 
    row++;
  } 
}

Но меня спросилиO(log (MxN)) == O(Log(n)) решение. Есть идеи??

Ты имеешь в видуO(log MxN) ? BrokenGlass
Гарантируется, что первый элемент каждой строки будет больше, чем последний элемент в предыдущей строке? (Как в вашем примере) В этом случае проблема тривиальна с помощью модифицированного бинарного поиска BrokenGlass
@Yoel: Ну, это может быть огромным, только целые числа, могут иметь отрицательные числа. Что-то конкретное, что вы ищете? noMAD
@ BrokenGlass: Нет, это вообще не гарантируется. Единственное условие - строки сортируются в порядке возрастания, как и столбцы. noMAD
Что вы знаете о входящей матрице, кроме того, что она сортируется (например, размер строки / столбца, perhpas?) Jordan

Ваш Ответ

5   ответов
4

Учитывая матрицу X и число y, вы можете выполнить бинарный поиск для y в средней строке X и разделить матрицу на четыре части так, чтобы:

A|B
---
C|D

все элементы в A меньше, чем y, все элементы в D больше, чем y, и y может быть в B и C. Итеративно найдите y в B и C.

Поскольку высота (A) = высота (B) \ прибл = высота (C) = высота (D), размер (X) = 2 * (размер (B) + размер (C)). Таким образом, полученная сложность, если O (logn).

def find(X,y):
    a,b = X.shape
    i = a /2
    j = binsearch(X[i,:], y)
    if X[i,j]==y:
        return True
    else:
        return find( X[ (i+1):a, 0:(j-1)], y ) or find( X[ 0:i, j:b], y )
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceededleetcode.com/2010/10/searching-2d-sorted-matrix-part-ii.html
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded noMAD
73

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

enter image description here

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

Для прямоугольной матрицы растяните квадратную картинку и установите дополнительные допущения соответственно. Здесь у нас есть мин (N, M) отсортированных подмассивов размера max (N, M) / мин (N, M) каждый. Лучший способ поиска здесь - использовать линейный поиск, чтобы найти один или несколько вложенных массивов, которые могут содержать заданное значение, а затем использовать бинарный поиск внутри этих вложенных массивов. В худшем случае необходимо выполнить бинарный поиск в каждом подмассиве. Сложность O (мин (N, M) * (1 + log (макс (N, M) / мин (N, M)))). Таким образом, для исходной (более сложной) задачи с прямоугольной матрицей мы не можем получить решение лучше, чем O (min (N, M) * (1 + log (max (N, M)) - log (min (N, M))) ).

Error: User Rate Limit ExceededCompetence Point
Error: User Rate Limit ExceededthisError: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit ExceededM==NError: User Rate Limit ExceededO(min(N,M) * (1 + log(max(N,M)) - log(min(N,M)))).
2

и столбцы отсортированы, если мы посмотрим на первый элемент каждой строки, мы сможем найти, какой из них содержит искомое число. Затем, опять же, мы можем использовать тот факт, что элементы в каждой строке отсортированы и найти это число.
Самый быстрый алгоритм поиска, который я знаю, это двоичный поиск, который имеет сложность O (log n), поэтому общая сложность будет O (log m + log n).
Вот пример, предположим, что мы ищем 28:

 1  2  3  4  5  6  7  8  9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
We do a binary search over the elements of the first column (1, 11, 21, 31, 41) and find that the row is the third, because its first element is smaller than our number but the next row's first element is larger. Number of steps: 2 (21, 31, found) We do a binary search again over the third row (21, 22, 23, 24, 25, 26, 27, 28, 29, 30) and find our number. Number of steps: 2 - 3 (25, 27 or 28, found)
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded noMAD
Error: User Rate Limit ExceededO(MLog N)Error: User Rate Limit Exceeded(M)Error: User Rate Limit Exceeded(log N). noMAD
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
0

что это можно сделать за время O (log (n * n) * log (n)), где n - нет. из строк квадратной матрицы.

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

Теперь рекурсивно ищите в подматрице (вверху справа) и в подматрице (внизу слева).

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

Итак, Временная сложность = O (log (n)log(nп)).

Пожалуйста, исправьте, если что-то не так.

Ссылки - [Книга] Взлом интервью по кодированию (Вопрос 11.6)

6

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

Проект доказательства того, что O (n) является оптимальным: рассмотрим следующую матрицу:

1     2     3     4     5     6 … (n-2)  (n-1) (n+1)
2     3     4     5     6     7 … (n-1)  (n+1) (n+2)
3     4     5     6     7     8 … (n+1)  (n+2) (n+3)
…     …     …     …     …     … … …      …     …
(n-2) (n-1) …     …     …     … … …      …     (2n-1)
(n-1) (n+1) …     …     …     … … …      …     2n
(n+1) (n+2) …     …     …     … … (2n-1) 2n    (2n+1)

Если вы ищетеn в этой матрице вы должны проверить хотя бы один раз для каждой строки, еслиn в ряд, потому чтоn может быть в любом ряду. (Доказательство не полное, но вот идея)

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded noMAD
Error: User Rate Limit ExceedednError: User Rate Limit ExceededT(n)Error: User Rate Limit Exceededn^2Error: User Rate Limit Exceededn/2Error: User Rate Limit Exceededn^2/4Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded

Похожие вопросы