Go4Expert (http://www.go4expert.com/)
-   Java (http://www.go4expert.com/forums/java/)
-   -   homework at complexity (http://www.go4expert.com/forums/homework-at-complexity-t22312/)

 Noam 4Jun2010 16:16

homework at complexity

hey, just got this assignment at complexity:
input is a nXn array, filled with 0's and 1's.
need to find "sink" - a 'k' row filled entirely with 0's, a 'k' column filled with 1's, except for (k,k) which is 0.
the method is called using
public int isSink(int[][] mat)
returns 'k' is there is one, -1 if false.
Code:

```0 1 1 0 0 0 0 0 1 1 1 0 0 1 0 0 returns 1```
this is my solution:
Code:

```        public int isSink (int[][] mat) {                 //int found = -1;                 int i,j;                 for (i = 0;i<mat.length;i++) {                         boolean flag = true;                         if (mat[i][i] == 0 && mat[i][0] == 0 && (mat[0][i] == 1 || i == 0)) {                                 for (j = 0;flag && j < mat.length;j++) {                                         if (mat[i][j] !=0)                                                 flag = false;                                         else if (mat[j][i] != 1)                                                 if (j!=i)                                                         flag = false;                                 }                                 if (flag) return i;                         }                                         }                 return -1;         }```
however, the teacher told us to make it with complexity of O(n), and i can't make it any less than O(n^2)
any help?

 All times are GMT +5.5. The time now is 21:11.