C code with O(n) complexity


  • 0
    W

    Since indexRet goes from 0 to len, this code just go through the string once, so its O(n).
    the key point is to calculate the jump value

    jump[2] = {2*(nRow-1-i), 2*i}
    

    besides the first row and last row, any other row goes its index by adding jump[0], jump[1], jump[0]....
    and the first and last row go their indexes by adding 2*(nRow-1),2*(nRow-1)....So for the first and last row, the jump[2] becomes

    jump[2] = { 2*(nRow-1), 2*(nRow-1) };
    

    You can draw a graph and then count the index, its easy to see.

    Here is the code:

    char* convert(char* s, int numRows) {
    	int len = strlen(s);
    	int n = numRows;
    	char *ret = (char*)malloc(len + 1);
    	int indexRet = 0;	
    	int jump[2];
    	int i, j, k;
    
    	if (n == 1) {
    		free(ret);
    		return s;
    	}
    	ret[len] = 0;
    	for (i=0; i < n; i++) {
    		jump[0] = 2 * (n - 1 - i);
    		jump[1] = 2 * i;
    		if (i == 0 || i == n - 1) 
    			jump[1] = jump[0] = 2 * (n - 1); 
    		for (j = i,k=0; j < len; j += jump[k], k = (k + 1) % 2) {
    			ret[indexRet++] = s[j];
    		}	
    	}
    	return ret;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.