1. We have moved from vBulletin to XenForo and you are viewing the site in the middle of the move. Though the functional aspect of everything is working fine, we are still working on other changes including the new design on Xenforo.
    Dismiss Notice

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