python - 在numpy数组中找到最大的正方形

Question

我正在尝试解决这个算法问题:在 numpy 数组中找到只有一个值的最大正方形。

示例图片:

我的代码花费了太多时间。有没有办法提高速度？

import numpy as np
answer = 0
def allsame(board):
    memory = board[0,0]
    board = np.matrix(board)
    for i in range(board[0].size):
        for j in range(board[0].size):
            if board[i,j] != memory: return False
    return True

def findLargestSquare(board):
    global answer
    list = []

    a = np.matrix(board)
    if a[0].size == 1 or a[:,1].size==1: return answer
    if a[1].size < a[:,1].size: ran = a[1].size
    else: ran = a[:,1].size
    for i in range(ran+1):
        for j in range(ran+1):
           if a[i:j,i:j].size > 0 and allsame(a[i:j,i:j])==True:
                    if a[i:j,i:j].size > answer:
                       list.append(a[i:j,i:j].size)
                       answer = a[i:j,i:j].size

    findLargestSquare(a[1:])
    return findLargestSquare(a[:,1:])
    return answer


#testBoard = [['x','o','g'],['b','a','j'],['u','q','p']]
testBoard = [['X','O','O','O','X'],['X','O','O','O','O'],['X','X','O','O','O'],['X','X','O','O','O'],['X','X','X','X','X']]
print(findLargestSquare(testBoard))

我把我的代码改成了自卷积的方法。你能看看哪部分是错的吗？

import numpy as np
import time
answer = 0


def findLargestSquare(board):
    global answer


    a = np.array(board)

    for k in reversed(range(a[0].size + 1)):
        conv_size = k
        for i in range(a[0].size - conv_size + 1):
            num = i
            for j in range(a[0].size - conv_size + 1):
                #print('i:', i, 'j:', j)
                print(a[i:i + conv_size, j:j + conv_size])
                #print('unique: ',np.unique(a[i:i+ conv_size,j:j+conv_size]).size)
                if(np.unique(a[i:i+ conv_size,j:j+conv_size]).size == 1):
                    #print("returning")
                    return len(a[i:i+ conv_size,j:j+conv_size])**2
                num = num + 1
                print("================")
    return len(a[i:i+ conv_size,j:j+conv_size])**2



# testBoard = [['x','o','g'],['b','a','j'],['u','q','p']]
testBoard = [['X', 'O', 'O', 'O', 'X'], ['X', 'O', 'O', 'O', 'O'], ['X', 'X', 'O', 'O', 'O'], ['X', 'X', 'O', 'O', 'O'],
             ['X', 'X', 'X', 'X', 'X']]


print(findLargestSquare(testBoard))

Answer 1

您可以在 O(n^2) 中完成它，而不是您当前的 O(n^4) (allsame() 是在 O(n^2) 中并被调用 O(n^2) 次:

使用新矩阵 best_size，这样 best_size[i, j] 应该包含原始棋盘中从 (i, j) 开始的最大正方形的大小.按照以下规则从末尾开始填充此矩阵:

def get_best_size(a, best_size, i, j):
    # TODO Handle boundaries: best_size = 1 there
    if not a[i, j] == a[i+1, j] == a[i, j+1]:
        return 1
    min_neighbor_best_size = min(best_size[i+1, j], best_size[i, j+1])
    if a[i, j] == a[i + min_neighbor_best_size , j + min_neighbor_best_size ]:
        return min_neighbor_best_size + 1
    else:
        return min_neighbor_best_size 

只需画出它就可以告诉您为什么这条规则有效。

然后您只需从数组的末尾迭代到开头，并记住最好的一个:

best = 0
for i in range(ran,-1,-1):
    for j in range(ran,-1,-1):
        best_size[i, j] =  get_best_size(a, best_size, i, j)
        best = max(best, best_size[i, j])
return best