时间戳

首页 > 解决方案 > 计算密度图 D

python - 计算密度图 D

问题描述

给定两个整数 n 和 r，使得 1 <= r < n，

一个大小为 nx n 的二维数组 W。

该数组的每个元素都是 0 或 1。

您的目标是使用 r 的半径计算数组 W 的密度图 D。

输出的密度图也是二维数组，

其中每个值表示指定半径内矩阵 W 中 1 的数量。

给定以下大小为 5 且半径为 1 的输入数组 W (n = 5, r = 1)

1 0 0 0 1
1 1 1 0 0
1 0 0 0 0
0 0 0 1 1
0 1 0 0 0

输出（使用 Python）：

3 4 2 2 1
4 5 2 2 1
3 4 3 3 2
2 2 2 2 2
1 1 2 2 2

逻辑：输入第一行，第一列的值为1。r值为1。所以我们应该检查1个右元素，1个左元素，1个顶部元素，左上角，右上角，底部，左下角和右下角并对所有元素求和.

不应使用任何 3rd 方库。

我使用 for 循环和内部 for 循环来完成它并检查每个元素。有更好的解决方法吗？

标签： python

解决方案

优化：对于 W 中的每个 1，更新位置的计数，它属于哪个邻域

尽管对于Wsize nxn，以下算法仍将采取 O(n^2) 步骤，但是如果 W 是稀疏的，即 1 的数量（例如k）<< nxn，那么代替所讨论rxrxnxn的方法的步骤，以下将采取nxn + rxrxk步骤，这要低得多如果k << nxn

给定r分配并W存储为

[[1, 0, 0, 0, 1],
 [1, 1, 1, 0, 0],
 [1, 0, 0, 0, 0],
 [0, 0, 0, 1, 1],
 [0, 1, 0, 0, 0]]

然后跟随

output = [[ 0 for i in range(5) ] for j in range(5) ]
for i in range(len(W)):
    for j in range(len(W[0])):
        if W[i][j] == 1:
            for off_i in range(-r,r+1):
                for off_j in range(-r,r+1):
                    if (0 <= i+off_i < len(W)) and (0 <= j+off_j < len(W[0])):
                        output[i+off_i][j+off_j] += 1

将所需的值存储在output

对于r = 1,output是必需的

[[3, 4, 2, 2, 1],
 [4, 5, 2, 2, 1],
 [3, 4, 3, 3, 2],
 [2, 2, 2, 2, 2],
 [1, 1, 2, 2, 2]]

推荐阅读