OH,my 1st "Your runtime beats 100.00% of c submissions" code...


  • 0
    Z
    bool search(int **a, int colnum, int rownum, int k)
    {
        if(colnum == 0 || rownum == 0) return false;
        int sx = colnum - 1, sy = 0;
        while ( sx >= 0 && sx<colnum && sy >= 0 && sy<rownum)
        {
            if (a[sy][sx]>k)
                --sx;
            else if ( a[sy][sx]<k)
                ++sy;
                else 
                return true;
        }
       
        return false;
    
    }
    bool searchMatrix(int** matrix, int matrixRowSize, int matrixColSize, int target) {
        return search(matrix,matrixColSize, matrixRowSize,target);
        
    }
    

    THX leetcode -_-


  • 2

    That is only because the test case favor your program. In the worst case scenario your solution is O(mn) which the is the same as the naive brute force solution.

    The worst case for your solution is like this:

    matrix = [[1,2,3,4,5,6....100000000]]

    target = 0

    In your solution, sx will traversal the whole matrix.

    Also you do not really need another function. And your

    sx >= 0 && sx<colnum && sy >= 0 && sy<rownum
    

    is wasting since

    sx < colnum and sy >= 0
    

    will always be true


  • 0
    Z

    ah,yes. you are right.
    I also throught it yesterday,it seems we can use binary search instead of '--sx;' and '++sy;'
    I will refine it ,Thank you


Log in to reply
 

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