Description
Let M be an N × N integer matrix, where each element in M is distinct, ensuring that no two elements are equal. Propose an algorithm that efficiently identifies the N largest elements among the elements of M. Furthermore, provide a proof of the correctness of this algorithm. Note that the algorithm does not need to preserve M’s initial state.
Example
-
Input
5
// N
1591325
// NXN matrix
26111627
37141828
48152130
10 11 20 23 50
Output
-
50 30 28 27 25
3
Consider an N × N matrix of integers where both its rows and columns are arranged in non-decreasing order. Propose an algorithm that, given such a matrix and an integer k, efficiently determines the position of k within the matrix. In cases where there are multiple occurrences of k in the matrix, the algorithm will identify one of them.
Input
5//N
1591325
26111627
37141828
48152130
10 11 20 23 50
8//K
Output
4 2 5
