Question

Элементами массива a[1..n] являются неубывающие массивы [1..m] целых чисел (a: array [1..n] of array [1..m] of integer; a[1][1] <= ... <= a[1][m], ..., a[n][1] <= ... <= a[n][m]).

Известно, что существует число, входящее во все массивы a[i] (существует такое х, что для всякого i из [1..n] найдётся j из [1..m], для которого a[i][j]=x).

Найти одно из таких чисел х.

Answer 1

Ответ:

Объяснение:

Для данного массива можно использовать алгоритм слияния k массивов, где k = n.

Алгоритм будет состоять из следующих шагов:

Создать новый массив b[1..n*m].

Создать массив указателей на первый элемент в каждом массиве [p1, p2, ..., pn] и инициализировать его значением 1 для всех элементов.

Для каждого i от 1 до n*m:

Найти минимальный элемент в массивах a[p1][1] до a[pn][m] и записать его в b[i].

Увеличить соответствующий указатель на 1: если b[i] был найден в a[pj][k], то увеличить pj на 1.

Вернуть массив b.

Алгоритм работает за O(nmlog(n)), так как на каждой итерации нужно находить минимальный элемент среди nm чисел, и это можно сделать за O(nlog(n)). Всего итераций nm, поэтому общая сложность алгоритма будет O(nm*log(n)).