N*M 网格中字典序最小的路径

Question

我在最近的一次采访中遇到了这个问题。我们有一个由数字组成的 N*M 网格，网格中的路径是节点，您 traverse.We 被赋予一个约束，我们只能在给定此网格的 grid.So 中向右或向下移动，我们需要找到字典上最小的路径，排序后，从网格的左上角到右下角
例如。如果网格是 2*2
4 3
5 1
那么根据问题，按字典顺序排列的最小路径是“1 3 4”。这样的问题怎么办？代码表示赞赏。提前致谢。

Answer 1

您可以使用Dynamic programming来解决这个问题。令 f(i, j) 为从 (i, j) 到 (N, M) 的最小词典路径（在对路径排序后），仅向右和向下移动。考虑以下重复：

f(i, j) = sort( a(i, j) + smallest(f(i + 1, j), f(i, j + 1)))

其中 a(i, j) 是网格中 (i, j) 处的值，smallest (x, y) returns x 和 y 之间较小的字典字符串. + 连接两个字符串，sort(str) 按词法顺序对字符串 str 排序。

重复的基本情况是：

f(N, M) = a(N, M)

当 i = N 或 j = M 时，重复频率也会发生变化（确保您看到了）。

考虑在C++中编写的以下代码：

//-- the 200 is just the array size. It can be modified

string a[200][200];             //-- represent the input grid
string f[200][200];             //-- represent the array used for memoization
bool calculated[200][200];      //-- false if we have not calculate the value before, and true if we have
int N = 199, M = 199;           //-- Number of rows, Number of columns


//-- sort the string str and return it
string srt(string &str){
    sort(str.begin(), str.end());
    return str;
}


//-- return the smallest of x and y
string smallest(string & x, string &y){
    for (int i = 0; i < x.size(); i++){
        if (x[i] < y[i]) return x;
        if (x[i] > y[i]) return y;
    }
    return x;
}



string solve(int i, int j){
    if (i == N && j == M) return a[i][j];       //-- if we have reached the buttom right cell (I assumed the array is 1-indexed
    if (calculated[i][j]) return f[i][j];       //-- if we have calculated this before 
    string ans;
    if (i == N) ans = srt(a[i][j] + solve(i, j + 1));       //-- if we are at the buttom boundary
    else if (j == M) ans = srt(a[i][j] + solve(i + 1, j));  //-- if we are at the right boundary
    else ans = srt(a[i][j] + smallest(solve(i, j + 1), solve(i + 1, j)));       
    calculated[i][j] = true;        //-- to fetch the calculated result in future calls
    f[i][j] = ans;
    return ans;
}


string calculateSmallestPath(){
    return solve(1, 1);
}

Answer 2

您可以应用动态规划方法在 O(N * M * (N + M)) 时间和 space 复杂度内解决此问题。

下面我会考虑，N是行数，M是列数，左上角的单元格坐标是(0, 0)，首先是行和第二列。

让每个单元格存储以排序顺序结束于该单元格的字典序最小路径。具有 0 索引的行和列的答案很简单，因为只有一种方法可以到达这些单元格中的每一个。对于其余单元格，您应该为顶部和左侧单元格选择最小路径并插入当前单元格的值。

算法为：

path[0][0] <- a[0][0]
path[i][0] <- insert(a[i][0], path[i - 1][0])
path[0][j] <- insert(a[0][j], path[0][j - 1])
path[i][j] <- insert(a[i][j], min(path[i - 1][j], path[i][j - 1])

Answer 3

如果没有重复数字，O (NM log (NM))也可以实现

直觉：

假设我将左上角 (a,b) 和右下角 (c,d) 的网格标记为 G(a,b,c,d)。由于您必须在 AFTER 对路径进行排序后获得字典序最小的字符串，因此目标应该是每次都在 G 中找到最小值。如果达到这个最小值，比方说，(i,j)，那么 G(i,b,c,j) 和 G(a,j,i,d) 对于我们的下一个分钟（路径）的搜索是无用的。也就是说，我们想要的路径的值永远不会在这两个格子中。证明？这些网格中的任何位置，如果遍历都不会让我们达到 G(a,b,c,d) 中的最小值（(i,j) 中的最小值）。而且，如果我们避免 (i,j)，我们构建的路径不能是字典序最小的。

因此，首先我们找到 G(1,1,m,n) 的最小值。假设它在 (i,j)。标记最小值。然后我们找出 G(1,1,i,j) 和 G(i,j,m,n) 中的 min 并为它们做同样的事情。继续这样做，直到最后，我们有 m+n-1 个标记的条目，它们将构成我们的路径。线性遍历原始网格G(1,1,m,n)，如果有标记则上报该值

方法：

每次在 G 中找到最小值的成本很高。如果我们将网格中的每个值映射到它的位置会怎样？ - 遍历网格并维护一个字典 Dict，键是 (i,j) 处的值，值是元组 (i,j)。最后，您将获得一个包含网格中所有值的键值对列表。

现在，我们将维护一个有效网格列表，我们将在其中找到适合我们路径的候选者。第一个有效网格将是 G(1,1,m,n)。

对键进行排序并从排序后的键集中的第一个值开始迭代S。

维护一棵有效网格树，T(G)，这样对于每个 G(a,b,c,d) in T、G.left = G(a,b,i,j) 和 G.right = G(i,j,c,d)，其中 (i,j) = location of min val in G(a,b,c,d)

现在的算法：

for each val in sorted key set S do
    (i,j) <- Dict(val)
    Grid G <- Root(T)
    do while (i,j) in G
       if G has no child do
           G.left <- G(a,b,i,j)
           G.right <- G(i,j,c,d)
       else if (i,j) in G.left
           G <- G.left
       else if (i,j) in G.right
           G <- G.right
       else 
           dict(val) <- null
           end do
       end if-else
    end do
end for
for each val in G(1,1,m,n)
    if dict(val) not null
        solution.append(val)
    end if
end for
return solution

Java代码：

class Grid{
    int a, b, c, d;
    Grid left, right;
    Grid(int a, int b, int c, int d){
        this.a = a;
        this.b = b;
        this.c = c;
        this.d = d;
        left = right = null;
    }
    public boolean isInGrid(int e, int f){
        return (e >= a && e <= c && f >= b && f <= d);
    }
    public boolean hasNoChild(){
        return (left == null && right == null);
    }
}
public static int[] findPath(int[][] arr){
        int row = arr.length;
        int col = arr[0].length;
        int[][] index = new int[row*col+1][2];
        HashMap<Integer,Point> map = new HashMap<Integer,Point>();
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                map.put(arr[i][j], new Point(i,j));
            }
        }
        Grid root = new Grid(0,0,row-1,col-1);
        SortedSet<Integer> keys = new TreeSet<Integer>(map.keySet());
        for(Integer entry : keys){
            Grid temp = root;
            int x = map.get(entry).x, y = map.get(entry).y;
            while(temp.isInGrid(x, y)){
                if(temp.hasNoChild()){
                    temp.left = new Grid(temp.a,temp.b,x, y);
                    temp.right = new Grid(x, y,temp.c,temp.d);
                    break;
                }
                if(temp.left.isInGrid(x, y)){
                    temp = temp.left;
                }
                else if(temp.right.isInGrid(x, y)){
                    temp = temp.right;
                }
                else{
                    map.get(entry).x = -1;
                    break;
                }
            }

        }
        int[] solution = new int[row+col-1];
        int count = 0;
        for(int i = 0 ; i < row; i++){
            for(int j = 0; j < col; j++){
                if(map.get(arr[i][j]).x >= 0){
                    solution[count++] = arr[i][j];
                }
            }
        }
        return solution;
    }

space 复杂性由字典的维护构成 - O(NM) 和树的维护 - O(N+M)。总体：O(NM)

字典填充然后排序的时间复杂度- O(NM log(NM))；用于检查每个 NM 值的树 - O(NM log(N+M))。总体 - O(NM log(NM)).

当然，如果重复值，这将不起作用，因为从那时起我们将有多个 (i,j) 用于网格中的单个值，选择哪个的决定将不再是满足于贪婪的方法。

附加信息：我之前听说的与此类似的问题有一个额外的网格属性 - 没有重复的值，数字来自 1 to NM。在这种情况下，复杂性可以进一步降低到 O(NM log(N+M))，因为您可以简单地使用网格中的值作为数组的索引（不需要排序）而不是字典。

N*M 网格中字典序最小的路径

Lexographically smallest path in a N*M grid

algorithm

graph-theory

graph