A little optimization from the naive idea got AC slow though.


  • 0
    1. Based on the definition of vector multiplication, this piece of solution comes out:
    class Solution(object):
        def multiply(self, A, B):
            # brute force TLE
            aw, ah, bw, bh, answ, ansh = len(A[0]), len(A), len(B[0]), len(B), len(B[0]), len(A)
            answer = [ [0 for i in xrange(answ)] for j in xrange(ansh) ]
            for i in xrange(ansh):
                for j in xrange(answ):
                    ansij = 0
                    for x in xrange(aw):
                        ansij += A[i][x] * B[x][j]
                    answer[i][j] = ansij
            return answer
    

    2.I notice it failed out of TLE when there are too many zeros during the calculation. So this time I preprocess A and B using a binary number where 1 and 0 represent nonzero and zero respectively.
    Then A & B shows us which element should be count which shouldn't.

    class Solution(object):
        def multiply(self, A, B):
            #using bitwise operation to minimize the number of calculation
            aw, ah, bw, bh, answ, ansh = len(A[0]), len(A), len(B[0]), len(B), len(B[0]), len(A)
            MA, MB = [0 for i in xrange(ah)], [0 for i in xrange(bw)]
            for i in xrange(ah):
                ta = 0
                for j in xrange(aw):
                    ta <<= 1
                    ta += 0 if A[i][j] == 0 else 1
                MA[i] = ta
            for i in xrange(bw):
                tb = 0
                for j in xrange(bh):
                    tb <<= 1
                    tb += 0 if B[j][i] == 0 else 1
                MB[i] = tb
            answer = [ [0 for i in xrange(answ)] for j in xrange(ansh) ]
            for i in xrange(ansh):
                for j in xrange(answ):
                    ansij, idxs = 0, MA[i] & MB[j]
                    idx = aw - 1
                    while idxs:
                        if idxs % 2:
                            ansij += A[i][idx] * B[idx][j]
                        idx, idxs = idx - 1, idxs >> 1
                    answer[i][j] = ansij
            return answer
    

Log in to reply
 

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