不确定它是否相关，但我想解决的问题是
~~~~~~~~~~~~~所有建筑物的最短距离~~~~~~~~~~~~~~~
你想在空旷的土地上建造一座房子，以最短的距离到达所有建筑物。您只能向上，向下，向左和向右移动。您将获得值为0,1或2的2D网格，其中：
每个0都标志着一片空地，你可以自由地经过。每1个标记一个您无法通过的建筑物。每个2都标志着你无法通过的障碍。
找到可以进入所有建筑物的空地的最小距离~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~
虽然我的解决方案在小输入上正常工作，但由于时间复杂性较大，因此输入时间较长。
但是我不确定这个解决方案的确切时间复杂度，并且想要正确理解这个解决方案的时间复杂度，以便我可以尽可能地尝试改进它。
我很确定外部循环的时间复杂度是O（MN）（M是总行数，N是cols的总数），因为我们循环遍历网格的所有位置，但我不确定是递归shortDist方法的时间复杂度。是O（MN）也是因为在最坏的情况下它会触及网格的每个位置，因此这个解决方案的总时间复杂度将是O（M ^ 2 * N ^ 2）或者是其它的东西，如果是这样的话如果有人可以解释我的话会很棒。
我的解决方案是
class Solution {
public:
int shortestDistance(vector<vector<int>>& grid) {
vector<std::pair<int,int>> dir = {{-1,0}, {1,0}, {0,-1}, {0,1}};
// pair(row, col) -> distance
map<std::pair<int,int>, int> cache;
vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), false)); // to check if we have already visited that location on the grid
int minDist = INT_MAX;
int maxCount =0;
// Finding number of 1's
for(int i =0; i< grid.size(); i++)
{
for(int y =0; y < grid[0].size(); y++)
{
if(grid[i][y] == 1)
{
maxCount++;
}
}
}
// For each 0 find the distance of each 1's and their count
// if the count of 1's is less than the number of 1's in the
// grid that grid position is not an acceptable pos
for(int i =0; i< grid.size(); i++)
{
for(int y =0; y < grid[0].size(); y++)
{
if(grid[i][y] == 0)
{
shortDist(grid, cache, dir, visited, i, y, 0);
int dist =0;
int count = cache.size();// number of 1's
if(count == maxCount)
{
// if we are here it implies that the empty land space have path to all the buildings
for(auto iter = cache.begin(); iter != cache.end(); iter++)
{
dist += iter->second;
}
if(dist < minDist)
{
minDist = dist;
}
}
cache.clear();
}
}
}
return minDist == INT_MAX ? -1 : minDist;
}
void shortDist(vector<vector<int>>& grid, map<std::pair<int,int>, int>& cache, vector<std::pair<int,int>>& dir, vector<vector<bool>>& visited, int row, int col, int dist)
{
if(row < 0 || col < 0 || row >= grid.size() || col >= grid[0].size())
{
return;
}
if(grid[row][col] == 2)
{
return;
}
if(grid[row][col] == 1)
{
auto found = cache.find(make_pair(row, col));
if(found == cache.end())
{
cache[(make_pair(row, col))] = dist;
}
else
{
found->second = min(found->second, dist);
}
return;
}
if(visited[row][col])
{
return;
}
visited[row][col] = true;
for(int i =0; i < dir.size(); i++)
{
int newRow = row + dir[i].first;
int newCol = col + dir[i].second;
shortDist(grid, cache, dir, visited, newRow, newCol, dist+1);
}
visited[row][col] = false;
}
};
据我所知，shortDist是主要的贡献者。
函数shortDist对于find有一个O（log（MN）），因为缓存最多可以包含rows * cols条目，（使用std::map，如果你有一个完美的哈希函数，使用std::unordered_map只有O（1））。然后你递归距离D = max（M，N），实际上你访问每个MN点。对于来自shortestDistance的每次呼叫的总计O（MN log（MN））。
在shortestDistance中，网格上的第二个循环在前两个循环中有O（MN），然后O（MN）用于在缓存上循环，给出O（M ^ 2 * N ^ 2），对shortDist的调用是O（M ^ 2N ^ 2 log（MN））。
如果使用另一个MN阵列直接查找该值，则可以保存日志（MN）。
实施优化。
你对shortDist的调用有太多参数。
dir向量应该是constexpr std :: array，因为它永远不会改变并且在所有搜索中使用。
Cache和visited应该是该类的成员，shortestDistance将为每个调用重置，如果不是，则只使用一次Solution的实例。
考虑到您执行此操作的次数，将您作为参数拖动网格似乎也很浪费。使它成为类ref或copy将解决这个问题。
然后shortDist只有一个合理的3个参数。
通过使网格成为一维并计算自己的索引，可以节省大量性能损失，从而减少shortDist中每次x，y查找从两个到一个内存访问。