检查给定矩阵中每一行是否包含从 1 到 N 的所有整数

---

矩阵是一种二维数据结构，由行和列组成，排列成网格状的方块。它常用于表示网格、多维数组和表格数据。

问题陈述

给定一个维度为 n*m 的矩阵，任务是检查矩阵的每一行是否包含从 1 到 n 的每个数字。行中数字的顺序无关紧要。如果此语句为真，则返回 true，否则返回 false。

例如

Input: mtx = [[1,2,3],[3,2,1],[2,1,3]]
Output: True

解释

给定一个大小为 3*3 的矩阵 mtx。为了返回 true，所有 3 行（即 n 行）必须包含从 1 到 3（即 1 到 m）的所有数字。此条件成立，因为每一行都包含数字 1、2 和 3。

例如

Input: mtx = [[2,1],[1,1]]
Output: False

解释

第一行满足每个行应包含 [1,m] 中的数字的条件。在本例中，m = 2。但是，在第二行中，数字 2 没有出现，而是数字 1 重复出现。这违反了主要条件。因此，程序应返回 false。

例如

Input: mtx = [[2]]
Output: False

解释

矩阵 mtx 仅包含 1 行和 1 列。预期该行包含数字 1，但事实并非如此，因此程序应返回 false；

解决方案方法 1

问题陈述包含一个主要条件，如下所示：

• 大小为 n * m 的矩阵的 n 行必须包含 [1,m] 中的所有数字。

• 因此，一个直观且蛮力的解决方案是迭代所有行并对当前行的元素进行排序。我们接下来检查该行中每列的元素是否比列索引大 1。

• 如果这对所有行都成立，则返回 true。否则返回 false。

• 由于我们正在迭代矩阵 mtx 的所有元素并对每一行进行排序，因此程序预计将在 (m*n*logn) 时间内运行。

伪代码

• 开始

• 初始化大小为 n*m 的矩阵 mtx。

• 遍历矩阵的每一行，并对其进行排序

• 遍历行的每个元素以检查当前元素是否比当前列索引大 1。

• 如果在任何时候前面的条件不成立，则返回 false

• 否则返回 true

• 停止

算法

• 初始化 vector<vector<int>>mtx

• for (i : 0 到 n - 1)

• sort(mtx[i])

• for (j : 0 到 m - 1)

• if (mtx[i][j] != j + 1)

• return false

• return true

示例：C++ 程序代码

以下 C++ 代码检查提供的矩阵的每一行是否包含从 1 到 m 的所有整数，并相应地打印 true 或 false。

// C++ program to verify that each row of the provided matrix contains all of the integers from 1 to m.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// main function
int main(){
   vector<vector<int>>mtx = {{1,2,3},{2,1,3},{3,2,1}};
   int n = mtx.size();
   int m = mtx[0].size();
   for (int i = 0; i < n; i++){
      sort(mtx[i].begin(), mtx[i].end());
      for (int j = 0; j < m; j++){
         if (mtx[i][j] != j + 1){
            cout << "false";
            return 0;
         }
      }
   }
   cout << "true";
   return 0;
}

输出

True

时间和空间复杂度分析

程序在 O(n*logn*m) 时间复杂度内运行，并且不需要任何辅助空间。

解决方案方法 2

为了使上述方法在时间复杂度方面更有效。我们使用行中元素在 [1, m] 范围内的条件。因此，我们跳过排序并执行以下步骤，而不是对每一行进行排序。

• 在迭代行时，使 mtx[i][current_element - 1] 位置处的元素为负数。

• 如果在对每个元素执行此操作后，矩阵中存在所有负整数，则所有行都应包含从 1 到 m 的数字。我们返回 true。

• 否则我们返回 false。

伪代码

• 开始

• 初始化大小为 n*m 的矩阵 mtx。

• 遍历每一行

• 对于当前行中的每个元素，使 mtx[row][element] 位置处的元素为负数。

• 如果该元素之前已经是负数，则返回 false

• 在使所有元素都为负数后返回 true

算法

• 初始化 vector<vector<int>>mtx

• for (i : 0 到 n - 1)

• for (j : 0 到 m - 1)

• if (mtx[i][mtx[i][j] - 1] < 0)

• return false

• mtx[i][mtx[i][j] - 1] = -mtx[i][mtx[i][j] - 1];

• return true

示例：C++ 程序代码

以下 C++ 代码验证矩阵的每一行是否包含从 1 到 m 的所有数字，其中 m 是矩阵中的列数。我们利用 m 列仅包含从 1 到 m 的数字这一事实。对于每一行，我们将索引等于当前元素值减 1（因为使用的是基于 0 的索引）处的元素标记为负数，以指示它以前已被访问过。这将意味着存在重复项，这进一步意味着矩阵无效，因为它不包含从 1 到 m 的所有数字。在这种情况下，我们返回 false。否则我们返回 true。

// C++ program to verify that each row of the provided matrix contains all of the integers from 1 to m.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// main function
int main(){
   vector<vector<int>> mtx = {{1, 2, 3}, {3, 1, 2}, {2, 1, 3}};
   int n = mtx.size();
   int m = mtx[0].size();
   // Iterate over each row of the matrix
   for (int i = 0; i < n; i++){
      // Iterate over each element in the row
      for (int j = 0; j < m; j++){
         // if the element is already negative that means there is repetition which should not been possible if all numbers from 1 to m are present
         if (mtx[i][mtx[i][j] - 1] < 0){
            cout << "false";
            return 0;
         }
         // Mark the element as visited by making it negative
         mtx[i][abs(mtx[i][j]) - 1] = -mtx[i][abs(mtx[i][j]) - 1];
      }
   }
   // If all elements are visited without encountering a repetition, the matrix is valid
   cout << "true";
   return 0;
}

输出

True

时间复杂度：O(n*m) - 代码的时间复杂度为 O(n * m)，其中 n 是矩阵中的行数，m 是列数。

代码使用嵌套循环来迭代矩阵的每个元素。外部循环迭代 n 次，内部循环迭代 m 次。因此，迭代总数为 n * m。

辅助空间：O(1) - 程序使用占用恒定额外空间的变量。

结论

本文讨论了一种朴素方法和一种有效方法来验证提供的矩阵的每一行是否包含从 1 到 m 的所有整数。解决方案方法包括伪代码、算法、C++ 程序以及时间和空间复杂度分析，以便更深入地理解。