Fastest python program in 44ms


  • 1
    S

    Since the rotation angle is 90 degree. Which means 360/90=4 parts need to move. So we only need to traverse 1/4 parts of the image and change value of the four parts in each iteration. For n being even and odd, the difference is to traverse one more column(same rows to traverse). Pretty straight forward huh? But not more elegant than other pythons hmmm

    class Solution:
            # @param matrix, a list of lists of integers
            # @return nothing (void), do not return anything, modify matrix in-place instead.
            def rotate(self, matrix):
                n=len(matrix)
                if n==1:
                    return
                if n%2==0:
                    for i in range(n/2):
                        for j in range(n/2):
                            matrix[i][j],matrix[j][n-1-i],matrix[n-1-i][n-1-j],matrix[n-1-j][i]=matrix[n-1-j][i],matrix[i][j],matrix[j][n-1-i],matrix[n-1-i][n-1-j]
                else:
                    for i in range(n/2):
                        for j in range(n/2+1):
                            matrix[i][j],matrix[j][n-1-i],matrix[n-1-i][n-1-j],matrix[n-1-j][i]=matrix[n-1-j][i],matrix[i][j],matrix[j][n-1-i],matrix[n-1-i][n-1-j]

  • 0
    L

    Hi, there. I did not see your code before but I found that our codes are really similar. Actually we do not need to deal with odd or even length, since if it is odd, we just need to leave the central element at the original position. Here is my code with 52ms. Please let me know what you think. Thanks!

    class Solution:
            # @param matrix, a list of lists of integers
            # @return nothing (void), do not return anything, modify matrix in-place instead.
        def rotate(self, matrix):
            length = len(matrix)
            if length == 1:
                return
            for i in range(length/2):
                for cur_y in range(i,length-i-1):
                    cur_x = i
                    matrix[cur_x][cur_y], matrix[len(matrix)-1-cur_y][cur_x], \
                        matrix[len(matrix)-1-cur_x][len(matrix)-1-cur_y], matrix[cur_y][len(matrix)-1-cur_x] = \
                        matrix[len(matrix)-1-cur_y][cur_x], matrix[len(matrix)-1-cur_x][len(matrix)-1-cur_y],\
                        matrix[cur_y][len(matrix)-1-cur_x],matrix[cur_x][cur_y]

  • 0
    L

    Also you should check this https://leetcode.com/discuss/27535/short-python-in-place-solution-50ms.
    Not sure if we are allowed to use rotate() function, but we are, wow, 5 lines concise code!


Log in to reply
 

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