Algorithmic puzzle

Май 12th, 2008 | by OleXaa |

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

  1. 9 Responses to “Algorithmic puzzle”

  2. By Ni@m on Май 12, 2008 | Reply

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

  3. By Vadim Voituk on Май 12, 2008 | Reply

    Квадратная версия бинарного поиска?

  4. By COTOHA on Май 13, 2008 | Reply

    с учётом того, что цифры не уникальны, то что является правильным ответом?

    индекс любого элемента с заданным значением или все индексы элементов с заданным значением?

  5. By Olexa on Май 14, 2008 | Reply

    индекс любого элемента с заданным значением - слишком просто
    интересует алгоритм нахождения всех элементов с заданным значением?

  6. By COTOHA on Май 14, 2008 | Reply

    как бы надо или свои вопросы придумывать или указывать источник.

    http://www.dev102.com/2008/05/12/a-programming-job-interview-challenge-3/

  7. By COTOHA on Май 14, 2008 | Reply

    там авторы вопроса разошлись во мнениях :) один говорит, что можно дать первый попавшийся, а второй говорит, что можно считать, что цифры уникальные

  8. By Olexa on Май 14, 2008 | Reply

    так, той пазл я взяв саме там(до речі, якщо цікаво, там є ще два завдання). Однак я дозволив собі трошки ускладнити завдання: елементи матриці далеко не унікальні,і хотілось би знайти алгоритм пошуку всіх елементів з заданим значенням. Сам рішення ще не маю. на разі, найкраще, що прийшло в голову- це ділити матрицю на чотири частини(бінарний пошук серед елементів діагоналі… на межі більше-менше.. коли один елемент більший ніж той, що необхідно знайти, а наступний вже менший).. потім частину(містить елементи зі значенням меншим ніж те, що шукається) викидую з пошуку, а решту знову ділю на частини..
    але підозрюю, що це далеко не оптимальний варіант

  9. By Григорii on Июнь 6, 2008 | Reply

    Хороший блог :) Люблю почитывать каждое утро (ну и в другое время тоже :)).

  10. By Алексей on Авг 10, 2008 | Reply

    Хорошо написано. Поставил у себя ссылочку

Post a Comment