homework at complexity

Discussion in 'Java' started by Noam, Jun 4, 2010.

  1. Noam

    Noam New Member

    Joined:
    Jun 4, 2010
    Messages:
    2
    Likes Received:
    0
    Trophy Points:
    0
    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 [COLOR="DarkOrange"]1[/COLOR] 1 0
    [COLOR="DarkOrange"]0 0 0 0[/COLOR]
    1 [COLOR="DarkOrange"]1[/COLOR] 1 0
    0 [COLOR="DarkOrange"]1[/COLOR] 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?
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice