Задача. Седловые точки
Задана матрица $K$, содержащая $n$ строк и $m$ столбцов. Седловой точкой этой матрицы назовем элемент, который одновременно является минимумом в своей строке и максимумом в своем столбце.
Найдите количество седловых точек заданной матрицы.
Входные данные
Первая строка содержит целые числа $n$ и $m$. $(1 \leq n, m \leq 750)$. Далее следуют $n$ строк по $m$ чисел в каждой. $j$-ое число $i$-ой строки равно $k_{ij}$. Все $k_{ij}$ по модулю не превосходят $1000$.
Выходные данные
Выведите количество седловых точек.
Тесты
| № | Ввод | Вывод |
| 1 | 2 2 0 0 0 0 |
4 |
| 2 | 2 2 1 2 3 4 |
1 |
| 3 | 5 5 100 -100 100 1000 110 10 -1000 100 -1000 110 100 -1000 100 100 110 1000 -1000 1000 1000 100 1000 -1000 1000 1000 -1000 |
1 |
| 4 | 4 4 1000 1000 100 100 1000 1000 1000 1000 100 100 100 1000 100 1000 1000 1000 |
4 |
| 5 | 2 3 1 -1 1 0 -1 0 |
2 |
| 6 | 5 1 -1 0 -1 0 -1 |
2 |
| 7 | 4 2 1 2 -2 1 -1 2 -2 -1 |
1 |
| 8 | 3 3 5 1 3 3 1 2 1 1 2 |
3 |
| 7 | 3 3 5 2 3 3 4 2 1 8 2 |
0 |
Решение
Чтобы посчитать количество седловых точек, нужно посчитать совпадения минимумов в каждой строке и максимумов в каждом столбце матрицы.
Вариант решения за $O\left(n^2\right)$
Для этого мы просто сравниваем каждый максимум с каждым минимумом и считаем их совпадения. В этом случае алгоритм будет выполнятся за $O(n^2)$, где $n$ это наибольшая из длин массивов. Это значит что при достаточно больших массивах программа будет работать непозволительно долго. Но такой подход достаточно прост в реализации и интуитивно понятен.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#include <iostream> #define N 750 using namespace std; int main() { int n, m, MIN[N], MAX[N]; cin >> n >> m; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { int input; cin >> input; if (i == 0) MAX[j] = input; else if (MAX[j] < input) MAX[j] = input; if (j == 0) MIN[i] = input; else if (MIN[i] > input) MIN[i] = input; } } int count = 0; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (MIN[i] == MAX[j]) count++; cout << count; return 0; } |
Вариант решения за $O\left(n\log n\right)$
В этом случае мы сортируем массивы, для установления взаимосвязи между элементами в них. А далее заведя два указателя на элементы массивов проверяем на равенство только не меньшие элементы от текущих в разных массивах. Если равных элементов окажется несколько подряд, то их количество будет равно произведению количества их повторений в каждом из массивов. Дойдя до конца одного из них нужно не забыть проверить остались ли в другом массиве равные последнему в пройденном элементы. Проверять стоит лишь не меньшие элементы. Таким алгоритмом мы проверяем совпадения линейно за $O(n)$, где $n$ это наибольшая из длин массивов, но для него необходимо отсортировать оба массива за $O(n\log n)$. Таким образом мы получаем вычислительную сложность $O(n\log n)$, что уже быстрее предыдущего варианта.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
#include <iostream> #define N 750 using namespace std; void merge_sort(int *arr, int n) { if (n == 1) return; int len_l = n / 2, len_r = n - len_l; int l[len_l], r[len_r]; for (int i = 0; i < n; i++) if (i < len_l) l[i] = arr[i]; else r[i - len_l] = arr[i]; merge_sort(l, len_l); merge_sort(r, len_r); int i = 0, j = 0; while (i < len_l && j < len_r) if (l[i] < r[j]) arr[i + j] = l[i++]; else arr[i + j] = r[j++]; while (i < len_l) arr[i + j] = l[i++]; while (j < len_r) arr[i + j] = r[j++]; } int main() { int n, m, MIN[N], MAX[N]; cin >> n >> m; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { int input; cin >> input; if (i == 0) MAX[j] = input; else if (MAX[j] < input) MAX[j] = input; if (j == 0) MIN[i] = input; else if (MIN[i] > input) MIN[i] = input; } } merge_sort(MAX, m); merge_sort(MIN, n); int i = 0, j = 0, count_i = 1, count_j = 1, counter = 0; while (i < n && j < m) { while (i < n-1 && MIN[i] == MIN[i+1]) { count_i++; i++; } while (j < m-1 && MAX[j] == MAX[j+1]) { count_j++; j++; } if (MIN[i] < MAX[j]) { i++; count_i = 1; } else if (MIN[i] > MAX[j]) { j++; count_j = 1; } else { counter += count_i * count_j; i++; j++; count_i = 1; count_j = 1; } } while (i < n && MIN[i] <= MAX[m-1]) { while (i < n-1 && MIN[i] == MIN[i+1]) { count_i++; i++; } if (MIN[i] == MAX[m-1]) { i++; counter += count_i; count_i = 1; } } while (j < m && MAX[j] <= MIN[n-1]) { while (j < m-1 && MAX[j] == MAX[j+1]) { count_j++; j++; } if (MAX[j] == MIN[n-1]) { j++; counter += count_j; count_j = 1; } } cout << counter; return 0; } |
Правильно ли вы асимптоты написали? Для первого наверно было бы правильно написать [latex]O(nm)[/latex], а во втором у вас сортировка слиянием для массива длинной [latex]n[/latex], так что у вас асимптота второго кода будет ну как минимум [latex]O(n\log n)[/latex], если я не прав прошу вас предоставить анализ времени работы.
Прошу прощения, пропустил закрывающий тег latex
Исправил.
Большое спасибо Руслан, соглашусь во втором случае оценка будет $O(n\log n)$, давайте попробуем порассуждать.
Насколько я помню оценка делается с точностью до константы.
В первом случае, выполнив оценку сверху и выбрав за $n$ максимум из $n$ и $m$, имеем вычислительную сложность $O(n^2)$.
Во втором случае вычислительная сложность будет $O(n\left(\log n + 1\right) + m\left(\log m + 1\right))$. Из $n$ и $m$ выберем максимум и обозначим за $n$, имеем:
$O(n\left(\log n + 1\right) + n\left(\log n + 1\right)) = O(2n\left(\log n + 1\right))$.
Отбросив константы имеем $O(n\log n)$.
Возможно в этих рассуждениях я допустил ошибку, подскажите, где?
Всё верно. И наверно стоит поподробнее описать алгоритмы
Хорошо, большое спасибо.
Поскольку у вас нет возможности корректировать свои комментарии, я позволил себе внести исправления. Нужно так — \log n, а не logn. Иван, исправьте, пожалуйста в тексте работы.
Слитно или раздельно? И Иван и Руслан сделали по ошибке на эту тему. Посмотрите пожалуйста эту и эту статьи.
Понял, исправил, прочёл статью, спасибо.