Это будет довольно большой вопрос с моей стороны, поскольку он требует глубокого и глубокого понимания проблемы, а также различных подходов, используемых до настоящего времени для оптимального решения.
В связи с этим позже я создам блог по этому вопросу, поскольку для написания содержимого и т. Д. Мне потребуется немного времени со стороны, поэтому я предоставлю ссылку на свой блог, как только она будет готова.
Тем не менее, я публикую это, чтобы мы могли начать обсуждение.
Первым делом первым:
Проблема заключается в следующем:
Напишите эффективный алгоритм, который ищет значение в таблице n x m (двумерный> массив). Эта таблица отсортирована по строкам и столбцам - то есть
Таблица [i] [j] ≤ Таблица [i] [j + 1]
Таблица [i] [j] ≤ Таблица [i + 1] [j].
Здесь следует отметить, что все строки и столбцы монотонно сортируются, т.е. все строки и столбцы сортируются в неубывающем (лексикографическом) порядке.
Чтобы ознакомиться с актуальной проблемой и обсудить ее, перейдите по следующей ссылке:
Примечание: у этого поста есть части 1,2 и 3.
Поиск 2D матрицы
Хонг Шен из Университета Гриффита, Австралия, 27 декабря 1995 г. опубликовал оптимальное решение для этой задачи - O (mlog (2n / m)) для последовательного алгоритма.
Хонг Шен - Обобщенный поиск оптимальной матрицы
С тех пор по этому вопросу было проведено множество дискуссий, блогов, а также статей и публикаций в Интернете и офлайн, но на сегодняшний день, насколько я знаю, O (((log (n)) 2) является лучше всего заявлено на этой статье с Улучшенный бинарный поиск .
Хотя подробный алгоритм не был предоставлен.
Теперь я сделал разные варианты решения этой проблемы в надежде довести оптимальное решение до лучшего, чем текущее (я думаю)
Однако я не так хорош в анализе временных сложностей алгоритмов.
Следующее - только один из них. По мере того, как мы будем принимать решения, я буду продолжать помогать другим и, таким образом, придумаю лучшее со всей вашей помощью.
Вот первый пример анализа сложности времени
/* NIAZ MOHAMMAD
IntPol2d.cpp
1. Find the interpolated mid along column
2. Compare key with each elements in row-wise
along the found mid column
3. IF failed
DO
RECURSIVE call to IntPol2d
a. IF(key > a[row][mid])
THEN SET l = mid + 1 and d = row - 1;
b. ELSE set r = mid -1 and u = row;
*/
bool intPol2d(int mat[][6], int M, int N, int target, int l, int u, int r, int d, int &targetRow, int &targetCol,int &count) {
count++;
if (l > r || u > d) return false;
if (target < mat[u][l] || target > mat[d][r]) return false;
int mid = l + ((target - mat[u][l])*(r-l))/(mat[d][r]-mat[u][l]);
int row = u;
while (row <= d && mat[row][mid] <= target)
{
if (mat[row][mid] == target)
{
targetRow = row;
targetCol = mid;
return true;
}
row++;
}
return intPol2d(mat, M, N, target, mid+1, u, r, row-1, targetRow, targetCol,count) ||
intPol2d(mat, M, N, target, l, row, mid-1, d, targetRow, targetCol,count);
}
Если вам требуется весь исполняемый код, пожалуйста, дайте мне знать .
Спасибо за ваше терпение и помощь и увидимся на форуме:
Примечание: @ Администраторы или модераторы, дайте мне знать, если это неправильное место для такого длинного вопроса, тогда я перейду к своему блогу.