Revizia anterioară Revizia următoare
Grozavesti
Observam ca daca avem la dispozitie o matrice NxN putem aduce orice element pe pozitia (1,1) in cel mult doua interschimbari (una pentru linii si una pentru coloane). Daca elementul minim se afla pe pozitia (i,j) interschimbam linia i si coloana j cu linia 1 si coloana 1. Astfel pentru fiecare x de la 1 la N vom plasa pe pozitia (x,x) cel mai mic element din submatricea avand coltul stanga sus (x,x). Acum problema se reduce la aflarea elementului minim din submatricea avand coltul stanga sus (x,x). Se poate implementa direct acest pas iterand prin toate valorile posibile si se obtine un algoritm de complexitate O(N3). Exista un algoritm mai bun, de complexitate O(N2logN) folosind un max-heap in care sunt introduse elementele din matrice, la fiecare interschimbare de linii sau coloane fiind actualizate elementele din max-heap.
