题目链接

上三角矩阵判定

题目描述

牛牛想知道一个 n 阶方阵是否为上三角矩阵。所谓上三角矩阵，是指矩阵中主对角线以下的元素都为 0，其中主对角线是从矩阵左上角到右下角的连线。

请你判断给定的方阵是否满足这一性质。

输入描述:

  • 第一行输入一个整数 n (1 <= n <= 100)。
  • 接下来 n 行，每行输入 n 个整数，用空格分隔。

输出描述:

  • 如果输入的方阵是上三角矩阵，则输出 "YES"；否则输出 "NO"。

示例1:

  • 输入: 
    3
1 2 3
0 4 5
0 0 6
  • 输出: YES
  • 说明: 该矩阵主对角线以下元素（a[1][0], a[2][0], a[2][1]）均为 0。

示例2:

  • 输入: 
    3
1 0 0
0 2 0
1 0 3
  • 输出: NO
  • 说明: 该矩阵在第3行第1列的元素 a[2][0] 为 1，不为0，故不是上三角矩阵。

解题思路

这道题的解法非常直观，就是严格按照上三角矩阵的定义进行检查。

  1. 理解定义: 上三角矩阵的关键性质是所有位于主对角线之下的元素都必须是0。对于一个矩阵 a，一个元素 a[i][j] (其中 i 是行索引，j 是列索引) 位于主对角线下方，当且仅当它的行索引大于列索引，即 i > j。

  2. 设置标志位: 我们可以使用一个布尔变量（例如 is_upper_triangular）作为标志。我们首先做一个乐观的假设，认为它是一个上三角矩阵，所以将这个标志位初始化为 true。

  3. 读取数据: 按照"先输入，再处理"的模式，我们先读取整数 n，然后创建一个 n x n 的二维数组，并将所有输入数据填充进去。

  4. 遍历检查:

    • 使用两层嵌套循环遍历整个二维数组。外层循环变量为 i（行），内层为 j（列）。
    • 在循环内部，我们只关心主对角线下方的元素。所以我们加入一个条件判断：if (i > j)。
    • 对于满足 i > j 的元素 a[i][j]，我们检查它是否为0。
    • 如果发现任何一个 a[i][j] != 0，那么这个矩阵就不可能是上三角矩阵。我们立刻将标志位 is_upper_triangular 设置为 false，并且可以立即停止后续的检查（使用 break 或 return），因为已经找到了反例。

  5. 输出结果: 当所有检查都完成后（或者因为找到反例而提前终止后），我们根据标志位 is_upper_triangular 的最终状态来输出结果。如果它仍然是 true，说明没有找到任何反例，矩阵是上三角矩阵，输出 "YES"。否则，输出 "NO"。

算法步骤概览:

  • 读入 n。
  • 创建 n x n 的二维数组 arr 并填充数据。
  • 初始化 is_upper = true。
  • for i from 0 to n-1:
    • for j from 0 to n-1:
      • 如果 i > j 并且 arr[i][j] != 0：
        • 设置 is_upper = false。
        • 跳出所有循环。
  • 如果 is_upper 为 true，输出 "YES"，否则输出 "NO"。

代码

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    
    vector<vector<int>> arr(n, vector<int>(n));
    
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> arr[i][j];
        }
    }
    
    bool is_upper_triangular = true;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) { // 优化: 只需检查 j < i 的部分
            if (arr[i][j] != 0) {
                is_upper_triangular = false;
                break; // 找到反例，跳出内层循环
            }
        }
        if (!is_upper_triangular) {
            break; // 跳出外层循环
        }
    }
    
    if (is_upper_triangular) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        int[][] arr = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j] = sc.nextInt();
            }
        }
        
        boolean isUpperTriangular = true;
        outerLoop: // 使用标签以便从内层循环直接跳出外层循环
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) { // 优化: 只需检查 j < i 的部分
                if (arr[i][j] != 0) {
                    isUpperTriangular = false;
                    break outerLoop; // 找到反例，终止所有循环
                }
            }
        }
        
        if (isUpperTriangular) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
}

n = int(input())
arr = []
for _ in range(n):
    arr.append(list(map(int, input().split())))

is_upper_triangular = True
for i in range(n):
    for j in range(i): # 优化: 只需检查 j < i 的部分
        if arr[i][j] != 0:
            is_upper_triangular = False
            break
    if not is_upper_triangular:
        break

if is_upper_triangular:
    print("YES")
else:
    print("NO")

算法及复杂度

  • 算法: 遍历检查。
  • 时间复杂度: 。在最坏的情况下（当矩阵确实是上三角矩阵时），我们需要遍历所有主对角线以下的元素。读取数据也需要 。
  • 空间复杂度: ，用于存储输入的 N x N 矩阵。