Пары одинаковых строк и колонок

Сложность: 🟡 Средняя

ℹ️ Описание

Дана матрица grid размером n x n, которая состоит из целых положительных чисел.

Посчитайте количество пар (r[i], c[j]), где строка r[i] равна колонке c[j]

Строка и колонка считаются равными, если они состоят из одинаковых элементов в одинаковом порядке.

⚠️ Ограничения

— Размер n находится в диапазоне от 1 до 200
— Значение каждого элемента в матрице находится в диапазоне от 1 до 10^5

1️⃣ Пример

Входные данные: grid = [[3,2,1],[1,7,6],[2,7,7]]

Ответ: 1

Есть одна одинаковая пара:
— (Строка 2, Колонка 1): [2,7,7]

2️⃣ Пример

Входные данные: grid = [[3,1,2,2],[1,4,4,5],[2,4,2,2],[2,4,2,2]]

Ответ: 3

Есть три одинаковые пары:
— (Строка 0, Колонка 0): [3,1,2,2]
— (Строка 2, Колонка 2): [2,4,2,2]
— (Строка 3, Колонка 2): [2,4,2,2]

✅ Решение

Чтобы решить задачу, нам нужно определить количество пар строк и столбцов в матрице, которые совпадают. Для этого мы используем два прохода: один для строк и один для столбцов.

Создаем карту подсчета строк:

Инициализируем пустую хеш-таблицу (объект в случае TypeScript) countMap, который будет хранить строки в виде ключей и их количество в виде значений.
Проходим по каждой строке матрицы. Для каждой строки создаем строковой ключ, конкатенируя все её элементы, разделенные точкой с запятой.
Если такой ключ уже существует в countMap, увеличиваем значение на единицу. В противном случае, устанавливаем значение равным единице.
Подсчет совпадающих столбцов:

Инициализируем счетчик counter, который будет хранить общее количество совпадающих пар.
Проходим по каждому столбцу матрицы. Для каждого столбца создаем строковой ключ, конкатенируя элементы каждого столбца по порядку, разделенные точкой с запятой.
Если такой ключ существует в countMap, добавляем значение из countMap к counter.
После прохода по всем столбцам возвращаем значение counter, которое будет равно количеству совпадающих пар строк и столбцов.

Посмотреть реализацию в блоге

#matrix #hash_table #medium