Задачи
June 5, 2022
Задача. Количество "уникальных" элементов в матрице
Дана двоичная матрица NxM, необходимо определить количество уникальных единиц в матрице.
Справка: "Уникальная" единица - это элемент матрицы mat[i][j] равный 1, когда как все остальные элементы в строке i и столбце j равны 0.
Пояснение: matrix[1][2] - уникальная единица.
Алгоритм
- Заведем два словаря rows, cols, где ключом будет номер строки/столбца, а значением - количество вхождений единицы в соответствующую строку/столбец.
- Также создадим список points, куда запишем координаты строки, столбца, элемент которого равен 1.
- Пройдем по матрице заполняя соответствующие словари и список.
- Пройдем по списку точек с единицами и выберем те из них, для которых значения обоих словарей равно 1.