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

Средняя

medium , matrix , hash table

17 June 2024

Описание задачи #

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

Посчитайте количество пар (r_i, c_j), где строка r_i равна колонке c_j

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

Ограничения #

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

Примеры #

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

Ответ: 1

Есть одна одинаковая пара:
- (Строка 2, Колонка 1): [2,7,7]
Входные данные: 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, которое будет равно количеству совпадающих пар строк и столбцов.

Реализация #

package main

import (
	"strconv"
	"strings"
)

func equalPairs(grid [][]int) int {
	countMap := make(map[string]int)
	builder := strings.Builder{}
	counter := 0

	for _, row := range grid {
		for _, col := range row {
			builder.WriteString(strconv.Itoa(col))
			builder.WriteString(";")
		}

		countMap[builder.String()]++
		builder.Reset()
	}

	for j := 0; j < len(grid); j++ {
		for i := 0; i < len(grid); i++ {
			builder.WriteString(strconv.Itoa(grid[i][j]))
			builder.WriteString(";")
		}

		counter += countMap[builder.String()]
		builder.Reset()
	}

	return counter
}

export const equalPairs = (grid: number[][]): number => {
    const countMap: Record<string, number> = {}
    let counter = 0

    grid.forEach(row => {
        let key = '';

        row.forEach(col => {
            key = `${key}${col};`
        })

        if (countMap[key]) {
            countMap[key]++
        } else {
            countMap[key] = 1
        }
    })

    for (let j = 0; j < grid.length; j++) {
        let key = '';

        for (let i = 0; i < grid.length; i++) {
            key = `${key}${grid[i][j]};`
        }

        if (countMap[key]) {
            counter += countMap[key]
        }
    }

    return counter
}

Оценка сложности #

По времени

Решение имеет временную сложность O(n²), так как мы проходим по всей матрице дважды.

По памяти

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

Оригинал задачи на Leetcode

Algorithmics