Устранить дубликаты из двоичной матрицы. Можно ли сделать это вовремя лучше, чем O (n ^ 2) - PullRequest
1 голос
/ 13 июня 2011

Вход [0 1 0 0 1, 1 0 1 1 0, 0 1 0 0 1, 1 1 1 0 0]

Ожидаемый выход [0 1 0 0 1, 1 0 1 1 0,1 1 1 0 0]

Решение, которое я мог бы придумать, было:

  1. Для каждой строки преобразовать их в десятичную (или использовать какой-либо метод контрольной суммы), принимает O (n)
  2. Это по существу преобразует матрицу в одномерный массив.
  3. Теперь используйте хеш-таблицу, просматривайте все элементы
  4. Отслеживайте дубликаты и сообщайте только уникальные элементы из этого массива.

Другие решения могут включать использованиеTRIE (или похожая структура).Но это все равно потребует O (n ^ 2)

Есть ли лучшее решение?

Ответы [ 2 ]

2 голосов
/ 13 июня 2011

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

РЕДАКТИРОВАТЬ: Поскольку все получили отрицательный голос, очевидно, кто-то, кто не понимает, что итерация N элементов является линейной независимо от того, как они расположены, я уточню.

При вычислении Big-O не учитывается порядок расположения коллекции в памяти, ЕСЛИ механизм хранения не обеспечивает эффективное постоянное время поиска.Массивы, независимо от того, сколько измерений считаются постоянными для извлечения.Итак, мы должны рассмотреть прохождение всей матрицы 5x5 как линейную операцию, потому что она, по сути, выполняет то же самое, как если бы вы получили одномерный массив из 25 объектов.

С этим вне пути:

  • Хэширование всех элементов, взятых по пять за раз, является линейным, потому что нам нужно прочитать каждый элемент ровно один раз, чтобы добавить их в хеш этой строки (который может быть таким же простым, как умножениекаждый элемент на 10 ^ x или 2 ^ x и добавление к промежуточному итогу).

  • Алгоритм BucketSort выполняется за время X * M для одномерного массива из X элементов с максимумомпорядок величины M. Так как X в этом случае является квадратным корнем из нашего общего N для всей операции, а максимальный порядок величины M в худшем случае также будет квадратным корнем из N, наша BucketSort будет выполняться за O (X* M) ~ = O (N) наихудший случай.

  • Итерация по отсортированным хэшам линейна, порядка квадратного корня из нашего общего числа N.

Итак,общая сложность этого алгоритма, выполненного на матрице из N значений, составляет примерно O (2N + sqrt (N)), что считается O (N).

0 голосов
/ 13 июня 2011

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...