檢查給定矩陣中每一行是否包含從 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++ 程式以及時間和空間複雜度分析，以便更深入地理解。