UniLecs #119. Седловой элемент матрицы
UniLecs
Задача: дана числовая матрицы N*M, где N - кол-во строк, M - столбцов. Необходимо найти седловые элемент заданной матрицы. (Седловой эл-т матрицы - элемент матрицы, ктр одновременно является минимальным элементов в соот.строке матрицы и максимальным элементов в соот.столбце матрицы). Выведите все седловые элементы заданной матрицы, если такого эл-та нет - выведите соот.сообщение.
Входные данные: числовая матрица N*M, где эл-ты матрицы - целые числа по модулю не превосходящие 10^4. N, M - от 1 до 10^3.
Вывод: седловые эл-ты матрицы, если такие имеются.
Пример:
[ { 1, 3, 5 },
{ 7, 9, 11 },
{ 13, 15, 17 } ]
Answer = 13
Идея: заведем два массива, где будем хранить минимальные значения для строк и для столбцов. Дальше по определению седлового элемента, если для какой то элемент в матрице будет равен минимальному значению для этой строки и макс.значению для столбца то мы выводим его.
Седловые точки имеют особое значение в теории игр. Например, в играх с нулевой суммой седловая точка платежной матрицы является равновесием Нэша.
Реализация:
https://gist.github.com/unilecs/b2b12f58f53b703aa9331d32f31d3672
Test: