Geek Answers Handbook

Matrix, question about using the algorithm

This was one of my interviews.

We have a matrix containing integers (without a given range). The matrix is ​​randomly filled with integers. We need to develop an algorithm that finds those rows that exactly match the column (s). We need to return the row number and column number to match. The order of matching items is the same. For example, If, the i-th row corresponds to the j-th column, and the i-th row contains the elements - [1,4,5,6,3]. Then the j-th column will also contain elements - [1,4,5,6,3]. Size nx n. My decision:

RCEQUAL(A,i1..12,j1..j2)// A is n*n matrix
if(i2-i1==2 && j2-j1==2 && b[n*i1+1..n*i2] has [j1..j2])
   use brute force to check if the rows and columns are same.
if (any rows and columns are same)
   store the row and column numbers in b[1..n^2].//b[1],b[n+2],b[2n+3].. store row no,
                                                 // b[2..n+1] stores columns that 
                                                 //match with row 1, b[n+3..2n+2] 
                                                 //those that match with row 2,etc..

else
   RCEQUAL(A,1..n/2,1..n/2);
   RCEQUAL(A,n/2..n,1..n/2);
   RCEQUAL(A,1..n/2,n/2..n);
   RCEQUAL(A,n/2..n,n/2..n);

Takes O (n ^ 2). It's right? If correct, is there a faster algorithm?

+5
source share
5

trie . trie.

, - . .

, , n ( trie n ) , . , , ...

+4

, / ( ) , .

( ), , " ": -)

+1

( ), ...

A - (, , ) NxN. A '- A. B , A A' ( [A A ']) RREF, .

:

A = 1 2
    3 4

A'= 1 3
    2 4

B = 1 2 1 3
    3 4 2 4

rref(B) = 1  0 0   -2
          0  1 0.5 2.5

, A A, A A '. rref (B).

A=
 1     2     3     4     5
 2     6    -3     4     6
 3     8    -7     6     9
 4     1     7    -5     3
 5     2     4    -1    -1

A'=
 1     2     3     4     5
 2     6     8     1     2
 3    -3    -7     7     4
 4     4     6    -5    -1
 5     6     9     3    -1

B = 
 1     2     3     4     5     1     2     3     4     5
 2     6    -3     4     6     2     6     8     1     2
 3     8    -7     6     9     3    -3    -7     7     4
 4     1     7    -5     3     4     4     6    -5    -1
 5     2     4    -1    -1     5     6     9     3    -1

rref(B)=
 1     0     0     0     0    1.000  -3.689  -5.921   3.080   0.495
 0     1     0     0     0        0   6.054   9.394  -3.097  -1.024
 0     0     1     0     0        0   2.378   3.842  -0.961   0.009
 0     0     0     1     0        0  -0.565  -0.842   1.823   0.802
 0     0     0     0     1        0  -2.258  -3.605   0.540   0.662

1.000 , . , 1.000 , , .

0

- , n ^ 2 , , , :)

0

IFF ...

, . , . O (n * logn).

, 0. , . , ( , ). 0 n-1 , 2 * n , , .

/ n, , O (1) .

, 2 O (nlogn), 2 * n * 1 O (nlogn). , , . n ** 3 .

0
source

More articles:


All Articles