对角线条中的导线矩阵

Question

我认为这个问题有一个简单的解决方案,几个for循环和一些花哨的计数器,但显然它更复杂.

所以我的问题是,你如何编写(在C中)对角线条中方形矩阵的函数遍历.

例:

1  2  3
4  5  6
7  8  9

必须按以下顺序遍历:

[1],[2,4],[3,5,7],[6,8],[9]

上面的每个条带都用方括号括起来.其中一个要求是能够区分条带.这意味着你知道什么时候开始新的条带.这是因为我必须为条带中的每个项目调用另一个函数,然后在新条带的开头之前调用.因此,没有代码重复的解决方案是理想的.

Answer 1

这是你可以使用的东西.只需将printfs替换为您实际想要做的事情.

#include <stdio.h>

int main()
{
    int x[3][3] = {1, 2, 3,
                   4, 5, 6,
                   7, 8, 9};
    int n = 3;
    for (int slice = 0; slice < 2 * n - 1; ++slice) {
        printf("Slice %d: ", slice);
        int z = (slice < n) ? 0 : slice - n + 1;
        for (int j = z; j <= slice - z; ++j) {
            printf("%d ", x[j][slice - j]);
        }
        printf("\n");
    }
    return 0;
}

输出:

Slice 0: 1
Slice 1: 2 4
Slice 2: 3 5 7
Slice 3: 6 8
Slice 4: 9

Answer 2

我会像这样移动行:

1  2  3  x  x
x  4  5  6  x
x  x  7  8  9

只需迭代列.实际上,这可以在没有物理移位的情

Answer 3

我们来看看矩阵元素是如何编入索引的.

(0,0)   (0,1)   (0,2)   (0,3)   (0,4)  
(1,0)   (1,1)   (1,2)   (1,3)   (1,4)  
(2,0)   (2,1)   (2,2)   (2,3)   (2,4)  

现在,让我们来看看条纹:

Stripe 1: (0,0)
Stripe 2: (0,1)    (1,0)  
Stripe 3: (0,2)    (1,1)    (2,0)
Stripe 4: (0,3)    (1,2)    (2,1)
Stripe 5: (0,4)    (1,3)    (2,2)
Stripe 6: (1,4)    (2,3)
Stripe 7: (2,4)

如果你仔细看看,你会注意到一件事.每个条带中每个矩阵元素的索引总和是恒定的.所以,这是执行此操作的代码.

public static void printSecondaryDiagonalOrder(int[][] matrix) {
    int rows = matrix.length;
    int cols = matrix[0].length;
    int maxSum = rows + cols - 2;

    for (int sum = 0; sum <= maxSum; sum++) {
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (i + j - sum == 0) {
                    System.out.print(matrix[i][j] + "\t");
                }
            }
        }
        System.out.println();
    }
}

它不是最快的算法(行(col*cols*(行+ cols-2))),但它背后的逻辑非常简单.

Answer 4

我在这里找到了这个：Traverse Rectangular Matrix in Diagonal strips

#include <stdio.h>

int main()
{
    int x[3][4] = { 1,  2,  3,  4,
                    5,  6,  7,  8,
                    9, 10, 11, 12};
    int m = 3;
    int n = 4;
    for (int slice = 0; slice < m + n - 1; ++slice) {
        printf("Slice %d: ", slice);
        int z1 = slice < n ? 0 : slice - n + 1;
        int z2 = slice < m ? 0 : slice - m + 1;
        for (int j = slice - z2; j >= z1; --j) {
                printf("%d ", x[j][slice - j]);
        }
        printf("\n");
    }
    return 0;
}

输出：

Slice 0: 1
Slice 1: 5 2
Slice 2: 9 6 3
Slice 3: 10 7 4
Slice 4: 11 8
Slice 5: 12

我发现这是一种非常优雅的方法，因为它只需要 2 个附加变量（z1 和 z2）的内存，这些变量基本上保存了有关每个切片长度的信息。外循环遍历切片编号 ( slice)，然后内循环遍历索引为： 的每个切片slice - z1 - z2。您需要的所有其他信息，然后是算法从哪里开始以及它如何在矩阵中移动。在前面的例子中，它将首先向下移动矩阵，到达底部后它将向右移动：(0,0) -> (1,0) -> (2,0) -> (2,1) - > (2,2) -> (2,3)。这种模式再次被变量 z1 和 z2 捕获。行与slice数字一起递增，直到它到达底部，然后z2将开始递增，这可用于保持行索引在其位置不变：slice - z2. 每个切片的长度通过slice - z1 - z2以下方式获知：，执行以下操作：（(slice - z2) - (slice - z1 -z2)减去算法按升序移动 m--，n++）结果z1其中是内部循环的停止标准。只保留了列索引，这很方便地继承自 j 到达底部后保持不变的事实，之后列索引开始增加。

前面的算法仅从左上角 (0,0) 开始按升序从左到右移动。当我需要这个算法时，我还需要从左下角 (m,n) 开始按降序搜索矩阵。因为我对算法非常着迷，所以我决定深入研究并调整它：

• 切片长度再次通过以下方式知道： slice -z1 - z2
• 切片的起始位置为：(2,0) -> (1,0) -> (0,0) -> (0,1) -> (0,2) -> (0,3)
• 每个切片的移动是m++和n++

我发现将其描述如下非常有用：

• slice=0 z1=0 z2=0 (2,0) (列索引= rowindex - 2)
• slice=1 z1=0 z2=0 (1,0) (2,1) (列索引= rowindex - 1)
• slice=2 z1=0 z2=0 (0,0) (1,1) (2,2) （列索引= rowindex + 0）
• slice=3 z1=0 z2=1 (0,1) (1,2) (2,3) （列索引= rowindex + 1）
• slice=4 z1=1 z2=2 (0,2) (1,3) （列索引= rowindex + 2）
• slice=5 z1=2 z2=3 (0,3) (列索引= rowindex + 3)

推导以下内容：（j = (m-1) - slice + z2使用 j++）使用切片长度的表达式使停止标准：((m-1) - slice + z2)+(slice -z2 - z1)结果为：(m-1) - z1 我们现在有了内部循环的参数：for (int j = (m-1) - slice + z2; j < (m-1) - z1; j++)

行索引由 j 知道，我们再次知道列索引仅在 j 开始恒定时才开始递增，因此再次在表达式中包含 j 不是一个坏主意。从上面的总和之间的差异我注意到差异总是等于j - (slice - m +1)，在其他一些情况下测试这个我相信这将适用于所有情况（我不是数学家;P）以及下降运动的算法从左下角开始如下所示：

#include <stdio.h>

int main()
{
    int x[3][4] = { 1,  2,  3,  4,
                    5,  6,  7,  8,
                    9, 10, 11, 12};
    int m = 3;
    int n = 4;
    for (int slice = 0; slice < m + n - 1; ++slice) {
        printf("Slice %d: ", slice);
        int z1 = slice < n ? 0 : slice - n + 1;
        int z2 = slice < m ? 0 : slice - m + 1;
        for (int j = (m-1) - slice + z2; j <= (m-1) - z1; j++) {
                printf("%d ", x[j][j+(slice-m+1)]);
        }
        printf("\n");
    }
    return 0;
}

现在我把其他两个方向留给你 ^^（只有在顺序实际上很重要时才重要）。

这个算法非常令人费解，即使你认为你知道它是如何工作的，它仍然会咬你的屁股。但是我认为它非常漂亮，因为它确实像您期望的那样在矩阵中移动。如果有人对算法有更多了解，例如名称，我很感兴趣，所以我可以看看我在这里所做的是否真的有意义，也许有更好的解决方案。