廢話不多說(shuō)，喊一句號(hào)子鼓勵(lì)自己：程序員永不失業(yè)，程序員走向架構(gòu)！本篇Blog的主題是螺旋矩陣，使用【二維數(shù)組】這個(gè)基本的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)
螺旋矩陣【EASY】
二維數(shù)組的結(jié)構(gòu)特性入手
題干
解題思路
根據(jù)題目示例 matrix = [[1,2,3],[4,5,6],[7,8,9]] 的對(duì)應(yīng)輸出 [1,2,3,6,9,8,7,4,5] 可以發(fā)現(xiàn)，順時(shí)針打印矩陣的順序是 “從左向右、從上向下、從右向左、從下向上” 循環(huán)。
因此，考慮設(shè)定矩陣的 “左、上、右、下” 四個(gè)邊界，模擬以上矩陣遍歷順序，算法流程：
- 空值處理： 當(dāng) matrix 為空時(shí)，直接返回空列表 [] 即可。
- 初始化： 矩陣 左、右、上、下 四個(gè)邊界 l , r , t , b ，用于打印的結(jié)果列表 res 。
-
循環(huán)打印： “從左向右、從上向下、從右向左、從下向上” 四個(gè)方向循環(huán)打印。
- 根據(jù)邊界打印，即將元素按順序添加至列表 res 尾部。
- 邊界向內(nèi)收縮 1 （代表已被打?。?。
- ** 判斷邊界是否相遇**（是否打印完畢），若打印完畢代表下一個(gè)方向無(wú)需打印，則跳出。
- 返回值： 返回 res 即可。
整體的打印過(guò)程
代碼實(shí)現(xiàn)
基本數(shù)據(jù)結(jié)構(gòu)：數(shù)組
輔助數(shù)據(jù)結(jié)構(gòu)：無(wú)
算法：無(wú)
技巧：無(wú)
import java.util.*;
public class Solution {
/**
* 代碼中的類(lèi)名、方法名、參數(shù)名已經(jīng)指定，請(qǐng)勿修改，直接返回方法規(guī)定的值即可
*
*
* @param matrix int整型二維數(shù)組
* @return int整型ArrayList
*/
public ArrayList<Integer> spiralOrder (int[][] matrix) {
// 1 入?yún)⑴袛?，如果為空?shù)組，返回空集合
if (matrix.length < 1) {
return new ArrayList<Integer>();
}
// 2 定義四條邊及返回值
ArrayList<Integer> result = new ArrayList<Integer>();
int left = 0;
int right = matrix[0].length - 1;
int top = 0;
int bottom = matrix.length - 1;
// 3 循環(huán)打印四條邊
while (true) {
// 3-1 從左向右打印,明確左右邊界，打印完后上邊界向下移動(dòng),并判斷是否有必要繼續(xù)從上到下打印
for (int i = left; i <= right; i++) {
result.add(matrix[top][i]);
}
if (++top > bottom) {
break;
}
// 3-2 從上向下打印,明確上下邊界，打印完后右邊界向左移動(dòng),并判斷是否有必要繼續(xù)從右到左打印
for (int i = top; i <= bottom; i++) {
result.add(matrix[i][right]);
}
if (left > --right) {
break;
}
// 3-3 從右向左打印,明確左右邊界，打印完后下邊界向上移動(dòng),并判斷是否有必要繼續(xù)從下到上打印
for (int i = right; i >= left; i--) {
result.add(matrix[bottom][i]);
}
if (top > --bottom) {
break;
}
// 3-4 從下向上打印,明確上下邊界，打印完后左邊界向右移動(dòng),并判斷是否有必要繼續(xù)從左到右打印
for (int i = bottom; i >= top; i--) {
result.add(matrix[i][left]);
}
if (++left > right) {
break;
}
}
return result;
}
}
++top > bottom 等價(jià)于先給 top 自增 1 ，再判斷++top > bottom 邏輯表達(dá)式
復(fù)雜度分析
- 時(shí)間復(fù)雜度 O(MN) ： M,N分別為矩陣行數(shù)和列數(shù)。
- 空間復(fù)雜度 O(1) ： 四個(gè)邊界 l , r , t , b 使用常數(shù)大小的額外空間。
旋轉(zhuǎn)圖像
和螺旋矩陣類(lèi)似，也是對(duì)一圈數(shù)值做處理
題干
解題思路
由原題知整體的旋轉(zhuǎn)公式如下：
如果可以使用輔助矩陣則按如下方式修改即可：
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
// 深拷貝 matrix -> tmp
int[][] tmp = new int[n][];
for (int i = 0; i < n; i++)
tmp[i] = matrix[i].clone();
// 根據(jù)元素旋轉(zhuǎn)公式，遍歷修改原矩陣 matrix 的各元素
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
matrix[j][n - 1 - i] = tmp[i][j];
}
}
}
}
考慮不借助輔助矩陣，通過(guò)在原矩陣中直接「原地修改」，實(shí)現(xiàn)空間復(fù)雜度 **O(1)**的解法。以位于矩陣四個(gè)角點(diǎn)的元素為例，設(shè)矩陣左上角元素 A 、右上角元素 B 、右下角元素 C 、左下角元素 D 。矩陣旋轉(zhuǎn) 90o 后，相當(dāng)于依次先后執(zhí)行 D→A，C→D, B→C, A→B 修改元素，即如下「首尾相接」的元素旋轉(zhuǎn)操作：
如上圖所示，由于第 1 步 D→A已經(jīng)將 A覆蓋（導(dǎo)致 A 丟失），此丟失導(dǎo)致最后第 4步 A→B無(wú)法賦值。為解決此問(wèn)題，考慮借助一個(gè)「輔助變量 tmp」預(yù)先存儲(chǔ) A ，此時(shí)的旋轉(zhuǎn)操作變?yōu)椋?br>
如上圖所示，一輪可以完成矩陣 4 個(gè)元素的旋轉(zhuǎn)。因而，只要分別以矩陣左上角 1/4的各元素為起始點(diǎn)執(zhí)行以上旋轉(zhuǎn)操作，
將這些元素旋轉(zhuǎn)完成即完成了整個(gè)數(shù)組的旋轉(zhuǎn)
具體來(lái)看，當(dāng)矩陣大小n為偶數(shù)時(shí)，行列均取前n/2，當(dāng)矩陣大小為奇數(shù)時(shí)，行取n/2，列?。╪+1）/2，因?yàn)闉槠鏀?shù)時(shí)，中間的元素不需要旋轉(zhuǎn)
代碼實(shí)現(xiàn)
基本數(shù)據(jù)結(jié)構(gòu)：數(shù)組
輔助數(shù)據(jù)結(jié)構(gòu)：無(wú)
算法：無(wú)
技巧：無(wú)
class Solution {
public void rotate(int[][] matrix) {
// 1 獲取數(shù)組長(zhǎng)度，依據(jù)替換順序位置matrix[i][j]->matrix[j][n-1-i]推導(dǎo)出ABCD位置
int n = matrix.length;
//int a=matrix[i][j];int b=matrix[j][n-1-i];int c=matrix[n-1-i][n-1-j];int d=matrix[n-1-j][i];
// 2 遍歷行列，行取n/2,列?。╪+1）/2 為了應(yīng)對(duì)奇數(shù)長(zhǎng)度的n
for (int i = 0; i < n / 2; i++) {
for (int j = 0; j < (n + 1) / 2; j++) {
// 2-1 暫存A的位置，用來(lái)后續(xù)替換B
int temp = matrix[i][j];
// 2-2 D替換A
matrix[i][j] = matrix[n - 1 - j][i];
// 2-3 C替換D
matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
// 2-4 B替換C
matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
// 2-5 A替換B
matrix[j][n - 1 - i] = temp;
}
}
}
}
復(fù)雜度分析
時(shí)間復(fù)雜度 O(N*N）： 其中 N 為輸入矩陣的行（列）數(shù)。需要將矩陣中每個(gè)元素旋轉(zhuǎn)到新的位置，即對(duì)矩陣所有元素操作一次，使用O(N*N）的時(shí)間
空間復(fù)雜度 O(1) ： 臨時(shí)變量 tmp使用常數(shù)大小的額外空間。值得注意，當(dāng)循環(huán)中進(jìn)入下輪迭代，上輪迭代初始化的 tmp占用的內(nèi)存就會(huì)被自動(dòng)釋放，因此無(wú)累計(jì)使用空間。
搜索二維矩陣【MID】
從下題矩陣的特性入手進(jìn)行查找
題干
解題思路
數(shù)組從左到右和從上到下都是升序的，如果從右上角出發(fā)開(kāi)始遍歷呢？會(huì)發(fā)現(xiàn)每次都是向左數(shù)字會(huì)變小，向下數(shù)字會(huì)變大，有點(diǎn)和二分查找樹(shù)相似。二分查找樹(shù)的話，是向左數(shù)字變小，向右數(shù)字變大。所以我們可以把 target 和當(dāng)前值比較。
- 如果 target 的值大于當(dāng)前值，那么就向下走。
- 如果 target 的值小于當(dāng)前值，那么就向左走。
- 如果相等的話，直接返回 true 。
也可以換個(gè)角度思考
- 如果 target 的值大于當(dāng)前值，也就意味著當(dāng)前值所在的行肯定不會(huì)存在 target 了，可以把當(dāng)前行去掉，從新的右上角的值開(kāi)始遍歷。
- 如果 target 的值小于當(dāng)前值，也就意味著當(dāng)前值所在的列肯定不會(huì)存在 target 了，可以把當(dāng)前列去掉，從新的右上角的值開(kāi)始遍歷。
看下邊的例子
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
如果 target = 9，如果我們從 15 開(kāi)始遍歷, cur = 15
target < 15, 去掉當(dāng)前列, cur = 11
[1, 4, 7, 11],
[2, 5, 8, 12],
[3, 6, 9, 16],
[10, 13, 14, 17],
[18, 21, 23, 26]
target < 11, 去掉當(dāng)前列, cur = 7
[1, 4, 7],
[2, 5, 8],
[3, 6, 9],
[10, 13, 14],
[18, 21, 23]
target > 7, 去掉當(dāng)前行, cur = 8
[2, 5, 8],
[3, 6, 9],
[10, 13, 14],
[18, 21, 23]
target > 8, 去掉當(dāng)前行, cur = 9, 遍歷結(jié)束
[3, 6, 9],
[10, 13, 14],
[18, 21, 23]
代碼實(shí)現(xiàn)
基本數(shù)據(jù)結(jié)構(gòu)：數(shù)組
輔助數(shù)據(jù)結(jié)構(gòu)：無(wú)
算法：無(wú)
技巧：無(wú)
import java.util.*;
public class Solution {
/**
* 代碼中的類(lèi)名、方法名、參數(shù)名已經(jīng)指定，請(qǐng)勿修改，直接返回方法規(guī)定的值即可
*
*
* @param target int整型
* @param array int整型二維數(shù)組
* @return bool布爾型
*/
public boolean Find (int target, int[][] array) {
// 1 入?yún)⑴袛?/span>
if (array.length < 1) {
return false;
}
// 2 定義行列邊界,從右上角出發(fā)，所以初始化為右上角位置
int right = array[0].length - 1;
int top = 0;
// 3 出發(fā)開(kāi)始遍歷,明確左右邊界的范圍
while (right >= 0 && top <= array.length - 1) {
int curValue = array[top][right];
if (curValue > target) {
// 3-1 如果當(dāng)前值大于目標(biāo)值，舍棄本列
right--;
} else if (curValue < target) {
// 3-2 如果當(dāng)前值小于目標(biāo)值，舍棄本行
top++;
} else {
// 3-3 如果當(dāng)前值等于目標(biāo)值，找到了目標(biāo)值
return true;
}
}
return false;
}
}
復(fù)雜度分析
- 時(shí)間復(fù)雜度 O(M+N) ： 只遍歷了一遍
- 空間復(fù)雜度 O(1) ：沒(méi)有使用額外空間。
拓展知識(shí)：二維數(shù)組
二維數(shù)組是一種常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)，它由多行和多列組成，可以用來(lái)存儲(chǔ)和處理二維數(shù)據(jù)集合，例如矩陣、表格、圖像、地圖等。在不同的編程語(yǔ)言中，定義和使用二維數(shù)組的方式可能有所不同，以下是一些常見(jiàn)編程語(yǔ)言中的示例。
C/C++:
// 定義一個(gè)3x3的整數(shù)二維數(shù)組
int matrix[3][3] = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
// 訪問(wèn)元素
int element = matrix[1][2]; // 獲取第二行第三列的元素，值為6
Python:
# 定義一個(gè)3x3的整數(shù)二維數(shù)組（使用嵌套列表）
matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
# 訪問(wèn)元素
element = matrix[1][2] # 獲取第二行第三列的元素，值為6
Java:
// 定義一個(gè)3x3的整數(shù)二維數(shù)組
int[][] matrix = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
// 訪問(wèn)元素
int element = matrix[1][2]; // 獲取第二行第三列的元素，值為6
常用方法和操作：
-
訪問(wèn)元素： 使用索引來(lái)訪問(wèn)二維數(shù)組中的特定元素，例如
matrix[i][j]，其中i表示行號(hào)，j表示列號(hào)。 -
遍歷二維數(shù)組： 使用嵌套循環(huán)來(lái)遍歷二維數(shù)組，通常使用一個(gè)循環(huán)迭代行，另一個(gè)循環(huán)迭代列，以訪問(wèn)所有元素。
-
初始化： 在定義二維數(shù)組時(shí)，可以初始化數(shù)組的值。可以使用嵌套列表（Python）、嵌套數(shù)組（C/C++）或類(lèi)似方式來(lái)初始化。
-
修改元素： 可以通過(guò)索引來(lái)修改特定元素的值，例如
matrix[i][j] = newValue。 -
獲取數(shù)組的行數(shù)和列數(shù)： 可以使用數(shù)組的長(zhǎng)度或大小來(lái)獲取行數(shù)和列數(shù)。
-
在算法中使用： 二維數(shù)組在解決各種問(wèn)題時(shí)非常有用，例如矩陣運(yùn)算、圖算法、迷宮求解等。
-
釋放內(nèi)存（C/C++）： 在使用動(dòng)態(tài)分配內(nèi)存創(chuàng)建二維數(shù)組時(shí)，需要謹(jǐn)慎釋放內(nèi)存以防止內(nèi)存泄漏。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-735390.html
二維數(shù)組是一種非常靈活和強(qiáng)大的數(shù)據(jù)結(jié)構(gòu)，可以在各種應(yīng)用中發(fā)揮作用，從簡(jiǎn)單的數(shù)據(jù)存儲(chǔ)到復(fù)雜的算法實(shí)現(xiàn)。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-735390.html
到了這里，關(guān)于【算法訓(xùn)練-數(shù)組 三】【數(shù)組矩陣】螺旋矩陣、旋轉(zhuǎn)圖像、搜索二維矩陣的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
