Вы можете сделать это за линейное время, вычислив хэш каждой строки, 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).