點選藍字關注我哦
以下是本期幹貨視訊 視訊後還附有文字版本哦
▼ 《名企高頻考點-C++ STL 二維vector的寫法，先行再列和先列再行周遊》 ▼ ps：請在WiFi環境下打開，如果有錢任性請随意
0. 概述
二維數組是日常開發中使用高頻的一種管理資料的方式，比如迷宮地圖，鄰接矩陣等，操作起來也非常友善。在面試中也經常被問到，本文主要對vector構造的二維數組進行說明。
1.傳統二維數組的缺陷
傳統定義二維數組的方式，采用宏定義給出二維數組的行和列，然後定義出二維數組并對其進行初始化，最後就是對該二維數組進行操作，比如：
#define ROW 5#define COL 5void Test2Array(){ int array[ROW][COL] = { { 0, 1, 0, 0, 0 }, { 0, 1, 0, 0, 0 }, { 0, 1, 1, 1, 0 }, { 0, 1, 0, 1, 0 }, { 0, 0, 0, 1, 0 } }; // 列印二維數組 for (int i = 0; i < ROW; ++i) { for (int j = 0; j < COL; ++j) { cout << array[i][j] << " "; } cout << endl; } cout << endl; }
該種方式使用起來确實比較友善，但缺陷是：數組被限制死了，隻能表示5行5列的數組，但有些情況下需要的可能是動态的二維數組，傳統二維數組就無能為力。
2. 使用vector定義二維數組
2.1 矩陣(每行元素個數相同)
(1)元素内容都相同：直接使用vector中vector 來進行構造
int main(){ size_t row, col; int val; cin>>row>>col>>val; // 建立一個row行col列的矩陣，并使用val進行填充 vector<vector<int>> v(row, vector<int>(col, val)); return 0;}
(2)元素内容不同：先建立好矩陣，然後給每行元素依次指派
int main(){ int row,col; cin>>row>>col; // 建立一個row行col列的二維數組，逐個給每行元素進行指派 vector<vector<int>> v(row, vector<int>(col)); // 将每行的元素指派為1~col for(int i = 0; i < v.size(); ++i) { for(int j = 0; j < v[i].size(); ++j) { v[i][j] = j+1; } } return 0;}
2.2 動态二維數組
先開辟行，再根據每列中具體元素個數來開辟空間以及給每行元素進行指派，比如：楊輝三角
/*楊慧三角的前5行0行：11行：1 12行：1 2 13行：1 3 3 14行：1 4 6 4 1觀察發現：第0列和對角線全部為1，其餘位置為上一行同列元素以及上一行同列前一個元素之和*/void PascalTriangle(int N){ vector<vector<int>> vv; // 先給出二維數組的行，此時每行還沒有空間 vv.resize(N); for (int i = 0; i < N; ++i) { // 将第i行元素個數設定為i+1，初始值用1填充 vv[i].resize(i + 1, 1); for (int j = 1; j < i; ++j) { vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1]; } } // 列印二維數組 for (int i = 0; i < N; ++i) { for (int j = 0; j <= i; ++j) { cout<" "; } cout << endl; }}
2.3 不确定行列個數
該種場景也比較常見，從問題給的描述中隻知道結果為二維數組，但是二維數組的行列需要根據題目的輸入來确定，直接無法确定。 此種方式的常見解法是：先構造一個空的二維數組，然後構造一個一維的不斷向二維數組中插入 例如：二叉樹的封層周遊
class Solution {public: vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> ret; if(nullptr == root) return ret; queue q; q.push(root); while(!q.empty()){ // 為了提高效率，先插入一個空的vector ret.push_back(vector<int>()); // 拿到數組的最後一行，借助引用直接在最後一行插入 vector<int>& level = ret.back(); // 本層中節點總的個數 size_t size = q.size(); for(int i = 0; i < size; ++i) { TreeNode* cur = q.front(); q.pop(); level.push_back(cur->val); if(cur->left) q.push(cur->left); if(cur->right) q.push(cur->right); } } return ret; }};
2.4 二維數組的誤用
用vector建立的二維數組，一般情況下是先給出有多少行，然後再對每行進行操作。最常見的誤用就是還沒有給每行配置設定空間，就直接對行進行操作而引起代碼崩潰。
void Test2Vector(){ vector<vector<int>> vv; vv.resize(5); // 二維數組總共有5行，但是每行現在還沒有空間 vv[0][0] = 10; // 此時直接操作每行中元素時會崩潰}
3. 面試題
二維數組先行後列周遊效率高
還是先列後行周遊效率高？
3.1 先行後列
先行後列是最常見的二維數組的周遊方式，而且效率非常高，因為二維數組的每一行都是一段連續的空間，根據局部性原理，作業系統再通路每個元素時，會将該元素附近多個元素一次性加載到緩存中來提高程式效率。
void Print2Vector(){ // 采用C++11提供的清單初始化構造二維數組，每行元素使用{1,2,3,4,5}進行填充 vector<vector<int>> vv(5, { 1, 2, 3, 4, 5 }); // 正常方式 for (size_t i = 0; i < vv.size(); ++i) { for (size_t j = 0; j < vv[i].size(); ++j) { cout << vv[i][j] << " "; } cout << endl; } cout << endl; // 采用範圍for列印 for (auto& rowV : vv){ for (auto e : rowV){ cout << e << " "; } cout << endl; } cout << endl;}程式輸出：1 2 3 4 51 2 3 4 51 2 3 4 51 2 3 4 51 2 3 4 51 2 3 4 51 2 3 4 51 2 3 4 51 2 3 4 51 2 3 4 5
3.2 先列後行 該種方式使用比較少，因為效率比較低，一般情況下适合矩陣使用場景。
void Print2Vector2(){ // 采用C++11提供的清單初始化構造二維數組，每行元素使用{1,2,3,4,5}進行填充 vector<vector<int>> vv(5, { 1, 2, 3, 4, 5 }); // 先行後列 for (size_t row = 0; row < vv.size(); ++row) { for (size_t col = 0; col < vv[i].size(); ++col) { cout << vv[row][col] << " "; } cout << endl; } cout << endl; // 先列後行 for (size_t col = 0; col < vv[0].size(); ++col) { for (size_t row = 0; row < vv.size(); ++row) { cout << vv[row][col] << " "; } cout << endl; } cout << endl;}程式輸出：1 2 3 4 51 2 3 4 51 2 3 4 51 2 3 4 51 2 3 4 51 1 1 1 12 2 2 2 23 3 3 3 34 4 4 4 45 5 5 5 5
4. 總結
本文主要介紹了vector構造二維數組的常見方式以及周遊，具體如下：
相信大家對二維數組的使用有進一步的了解，具體還應該根據實際情況選擇合适的構造方式。 最後介紹了二維數組行優先周遊以及列優先的周遊方式，以及兩種周遊方式的差別，希望通過本文學習，大家對于二維數組應用可以得心應手，謝謝。 作者：時亮益 稽核：王海斌 編輯：比特李哥
好看，就要點個"在看"