Траншея в 2-м массиве

Question

0

Предположим, что существует массив nxn. Как найти пару индексов я и j, таких, что;

A[i][j] < A[i+1][j], A[i][j] < A[i-1][j], A[i][j] < A[i][j+1],A[i][j] < A[i][j-1]

Все, что я мог подумать, это O (n ²) algo, который пересекает полный массив и находит элемент, основанный на данных условиях.

Можем ли мы предложить лучшее решение?

Rajeshwar Agrawal 27 янв. 2014, в 15:21

0

Какой у вас язык программирования ??
aksu 27 янв. 2014, в 14:12
1

C / C ++ Почему это важно? Вы можете дать алгоритм.
Rajeshwar Agrawal 27 янв. 2014, в 14:14

Теги:

arrays

multidimensional-array

c

search

1 ответ

gbtimmon · Answer 1 · 2014-01-27T13-04-00.000Z

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

По этой логике я уверен, что эта проблема должна иметь нижнюю границу O(n^2)