算法-螺旋矩阵

鹿酒 2022/1/8 算法

螺旋矩阵实现探讨

# 题目描述

给定一个m x n大小的矩阵（m行，n列），按螺旋的顺序返回矩阵中的所有元素。

数据范围：0 ≤ (m, n) ≤ 100，矩阵中任意元素都满足 |val| ≤ 100

要求：空间复杂度 O(nm)，时间复杂度 O(nm)

# 解法1

# 思路

数据按照蛇形前进，前进的任意方向时的下一步都有且只有两种情况，例如：

前进方向 == 右，下一步只可能是右 || 下，即x++ || y++ 前进方向 == 下，下一步只可能是下 || 左，即x-- || x++ 前进方向 == 左，下一步只可能是下 || 上，即x-- || y-- 前进方向 == 上，下一步只可能是上 || 右，即x++ || y--

由此蛇形前进就实现了，另外需要增加碰撞转向（下一步的值重复使用，改遍方向）

需要保存x,y的位置数组，然后与下一步的x,y进行重复检测。

# 代码

性能：运行时间：90ms 占用内存：8368KB

/**
 * 
 * @param matrix int整型二维数组 
 * @return int整型一维数组
 */
function spiralOrder( matrix ) {
    // write code here
    if(!matrix || matrix.length == 0) return []
    let data = [];
    const m = matrix.length, n = matrix[0].length;
    let x = 0, y = 0; // 当前头部数据位置
    let position = 0 // 0 右 1 下 2 左 3 上
    let indexData = [[0,0]]
    for(let i = 0; i < m*n; i++){
        let checkIndexData = indexData.map(e=>e.join()) // 历史位置数据
        if(position == 0){
            if(matrix[x][y+1] != undefined && checkIndexData.indexOf([x, y+1].join()) == -1){ // 校验
                indexData.push([x, y+1])
                position = 0
                y++
            }else if(matrix[x+1] != undefined){
                indexData.push([x+1, y])
                position = 1
                x++
            }
        }else if(position == 1){
            if(matrix[x+1] != undefined && checkIndexData.indexOf([x+1, y].join()) == -1){
                indexData.push([x+1, y])
                position = 1
                x++
            }else if(matrix[x][y-1] != undefined){
                indexData.push([x, y-1])
                position = 2
                y--
            }
        }else if(position == 2){
            if(matrix[x][y-1] != undefined && checkIndexData.indexOf([x, y-1].join()) == -1){
                indexData.push([x,y-1])
                position = 2
                y--
            }else if(matrix[x-1] != undefined){
                indexData.push([x-1,y])
                position = 3
                x--
            }
        }else if(position == 3){
            if(matrix[x-1] != undefined && checkIndexData.indexOf([x-1, y].join()) == -1){
                indexData.push([x-1,y])
                position = 3
                x--
            }else if(matrix[x][y+1] != undefined){
                indexData.push([x,y+1])
                position = 0
                y++
            }
        }
        data.push(matrix[indexData[i][0]][indexData[i][1]])
    }
    return data
}
module.exports = {
    spiralOrder : spiralOrder
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

# 优化

性能：运行时间：87ms 占用内存：8292KB

/**
 * 
 * @param matrix int整型二维数组 
 * @return int整型一维数组
 */
function spiralOrder( matrix ) {
    // write code here
    if(!matrix || matrix.length == 0) return []
    let data = [], 
        indexData = [[0,0]], // 历史位置数据
        x = 0, y = 0, // 当前头部数据位置
        position = 0; // 0 右 1 下 2 左 3 上
    for(let i = 0; i < matrix.length * matrix[0].length; i++){
        data.push(matrix[x][y])
        let checkIndexData = indexData.map(e=>e.join()) // 历史位置数据
        if(position == 0){
            if(matrix[x][y+1] != undefined && checkIndexData.indexOf([x, y+1].join()) == -1){ // 校验
                y++
                position = 0
            }else{
                x++
                position = 1
            }
        }else if(position == 1){
            if(matrix[x+1] != undefined && checkIndexData.indexOf([x+1, y].join()) == -1){
                x++
                position = 1
            }else{
                y--
                position = 2
            }
        }else if(position == 2){
            if(matrix[x][y-1] != undefined && checkIndexData.indexOf([x, y-1].join()) == -1){
                y--
                position = 2
            }else{
                x--
                position = 3
            }
        }else if(position == 3){
            if(matrix[x-1] != undefined && checkIndexData.indexOf([x-1, y].join()) == -1){
                x--
                position = 3
            }else{
                y++
                position = 0
            }
        }
        indexData.push([x,y])
    }
    return data
}
module.exports = {
    spiralOrder : spiralOrder
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

# 解法2

# 思路2

按照边框的画法，顺时针取值，外圈完了找内圈，例如：

3*4的矩阵，外圈四个方向长度分别是 [0, 0]-[x, 0] [x, 1]-[x, y] [x, y-1]-[0, x] [x-1, 0]-[1, 0]

然后四个方向的变量向内部缩紧1top++ right-- bottom-- left++

增加圈限制，防止数据重复，当top < x_length/2 && left < y_length/2

# 代码2

性能：运行时间：87ms 占用内存：8144KB

/**
 * 
 * @param matrix int整型二维数组 
 * @return int整型一维数组
 */
function spiralOrder( matrix ) {
    // write code here
    if(!matrix || matrix.length == 0) return []
    let data = [], 
        top = 0, bottom = matrix.length - 1, // 上下边距
        left = 0, right = matrix[0].length - 1; // 左右边距
    while(top<matrix.length/2 && left<matrix[0].length/2){
        // 上左-上右
        for(let i = left; i <= right; i++){
            data.push(matrix[top][i])
        }
        // 上右-下右
        for(let i = top+1; i <= bottom; i++){
            data.push(matrix[i][right])
        }
        // 下右-下左
        if(top != bottom){
            for(let i = right-1; i >= left; i--){
                data.push(matrix[bottom][i])
            }    
        }
        // 下左-上左
        if(left != right){
            for(let i = bottom-1; i >= top + 1; i--){
                data.push(matrix[i][left])
            }
        }
        top++
        bottom--
        left++
        right--
    }
    
    return data
}
module.exports = {
    spiralOrder : spiralOrder
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

# 总结

两种思路性能差距不大。

第一种更贴近我的思路。

鹿酒的博客