给定矩阵左上第Kth条对角线

原文:https://www . geeksforgeeks . org/kth-从给定矩阵的左上角开始对角化/

给定一个 N * N 维度的平方矩阵 M[ ][ ] ，任务是找到矩阵的 K ^第 条对角线，从左上角开始向右下角移动，并打印其内容。
示例:

输入: N = 3，K = 2，M[ ][ ] = {{4，7，8}，{9，2，3}，{0，4，1}
输出: 9 7
说明:
给定矩阵从左上角到右下角的 5 条可能对角线为:
1 - > {4}
2 - > {9，7}
3 - >
输入: N = 2，K = 2，M[ ][ ] = {1，5}，{9，4}}
输出: 1
解释:
对于给定矩阵，从左下到右上开始的 3 种可能对角线为:
1 - > {1}
2 - > {9，5}
3 - > {4}

天真方法:
解决这个问题最简单的方法是从给定矩阵的左上角到右下角生成所有对角线。生成第 K ^条对角线后，打印其内容。
时间复杂度:O(N²)
辅助空间: O(N)
高效途径:
以上途径可以通过避免遍历矩阵来优化。相反，找到 K ^第 对角线的边界，即左下和右上索引。获得这些索引后，只需遍历对角线的索引即可打印所需的对角线。
需要以下观察来找到对角线的位置:

如果((K–1):对角线为上对角线
左下边界=M【K–1】【0】
右上边界=M【0】【K–1】
如果 (K？N) :对角线为下对角线。
左下边界= M[N-1][K-N]
右上边界= M[K-N][N-1]

按照以下步骤解决问题:

• 如果(K–1)<N，设置起始行，起始行为K–1，列，起始列为 0 。


• 否则，将 startRow 设置为N–1， startCol 设置为K–N。


• 最后从M【startRow】【startCol】开始打印对角线的元素。

以下是上述方法的实现:

C++

// C++ implementation of
// the above approach
#include
using namespace std;
// Function returns required diagonal
void printDiagonal(int K, int N,
                vector >& M)
{
    int startrow, startcol;
    // Initialize values to
    // print upper diagonals
    if (K - 1         startrow = K - 1;
        startcol = 0;
    }
    // Initialize values to
    // print lower diagonals
    else {
        startrow = N - 1;
        startcol = K - N;
    }
    // Traverse the diagonal
    for (; startrow >= 0 && startcol         startrow--, startcol++) {
        // Print its contents
        cout <            <<" ";
    }
}
// Driver Code
int main()
{
    int N = 3, K = 4;
    vector > M = { { 4, 7, 8 },
                            { 9, 2, 3 },
                            { 0, 4, 1 } };
    printDiagonal(K, N, M);
    return 0;
}


Java 语言(一种计算机语言，尤用于创建网站)

// Java implementation of
// the above approach
import java.util.*;
class GFG{
// Function returns required diagonal
static void printDiagonal(int K, int N,
                          int [][]M)
{
    int startrow, startcol;
    // Initialize values to
    // print upper diagonals
    if (K - 1     {
        startrow = K - 1;
        startcol = 0;
    }
    // Initialize values to
    // print lower diagonals
    else
    {
        startrow = N - 1;
        startcol = K - N;
    }
    // Traverse the diagonal
    for(; startrow >= 0 && startcol           startrow--, startcol++)
    {
        // Print its contents
        System.out.print(M[startrow][startcol] + " ");
    }
}
// Driver Code
public static void main(String[] args)
{
    int N = 3, K = 4;
    int[][] M = { { 4, 7, 8 },
                  { 9, 2, 3 },
                  { 0, 4, 1 } };
    printDiagonal(K, N, M);
}
}
// This code is contributed by PrinciRaj1992


Python 3

# Python3 implementation of the
# above approach
def printDiagonal(K, N, M):
    startrow, startcol = 0, 0
    # Initialize values to prupper
    # diagonals
    if K - 1         startrow = K - 1
        startcol = 0
    else:
        startrow = N - 1
        startcol = K - N
    # Traverse the diagonals
    while startrow >= 0 and startcol         # Print its contents
        print(M[startrow][startcol], end = " ")
        startrow -= 1
        startcol += 1
# Driver code
if __name__ == '__main__':
    N, K = 3, 4
    M = [ [ 4, 7, 8 ],
          [ 9, 2, 3 ],
          [ 0, 4, 1 ] ]
    printDiagonal(K, N, M)
# This code is contributed by mohit kumar 29


C

// C# implementation of
// the above approach
using System;
class GFG{
// Function returns required diagonal
static void printDiagonal(int K, int N,
                          int [,]M)
{
    int startrow, startcol;
    // Initialize values to
    // print upper diagonals
    if (K - 1     {
        startrow = K - 1;
        startcol = 0;
    }
    // Initialize values to
    // print lower diagonals
    else
    {
        startrow = N - 1;
        startcol = K - N;
    }
    // Traverse the diagonal
    for(; startrow >= 0 && startcol           startrow--, startcol++)
    {
        // Print its contents
        Console.Write(M[startrow,startcol] + " ");
    }
}
// Driver Code
public static void Main(String[] args)
{
    int N = 3, K = 4;
    int[,] M = { { 4, 7, 8 },
                 { 9, 2, 3 },
                 { 0, 4, 1 } };
    printDiagonal(K, N, M);
}
}
// This code is contributed by PrinciRaj1992


java 描述语言

输出:

4 3


时间复杂度: O(N)
辅助空间: O(1)