我正在尝试解决这个算法问题:在 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))
最佳答案
您可以在 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
关于python - 在numpy数组中找到最大的正方形,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44427012/