Go4Expert

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 13:59.