Задачи
June 5, 2022

Задача. Количество "уникальных" элементов в матрице

Дана двоичная матрица NxM, необходимо определить количество уникальных единиц в матрице.

Справка: "Уникальная" единица - это элемент матрицы mat[i][j] равный 1, когда как все остальные элементы в строке i и столбце j равны 0.

Пример

1 0 0
0 0 1
1 0 0

Output: 1

Пояснение: matrix[1][2] - уникальная единица.

Алгоритм

  1. Заведем два словаря rows, cols, где ключом будет номер строки/столбца, а значением - количество вхождений единицы в соответствующую строку/столбец.
  2. Также создадим список points, куда запишем координаты строки, столбца, элемент которого равен 1.
  3. Пройдем по матрице заполняя соответствующие словари и список.
  4. Пройдем по списку точек с единицами и выберем те из них, для которых значения обоих словарей равно 1.

Детали смотрите ниже в коде.

Реализация

Test

https://dotnetfiddle.net/YUekyJ