【算法训练-数组 三】【数组矩阵】螺旋矩阵、旋转图像、搜索二维矩阵

这篇具有很好参考价值的文章主要介绍了【算法训练-数组 三】【数组矩阵】螺旋矩阵、旋转图像、搜索二维矩阵。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

废话不多说,喊一句号子鼓励自己:程序员永不失业,程序员走向架构!本篇Blog的主题是螺旋矩阵,使用【二维数组】这个基本的数据结构来实现
【算法训练-数组 三】【数组矩阵】螺旋矩阵、旋转图像、搜索二维矩阵,# 数组,算法,矩阵,java

螺旋矩阵【EASY】

二维数组的结构特性入手

题干

【算法训练-数组 三】【数组矩阵】螺旋矩阵、旋转图像、搜索二维矩阵,# 数组,算法,矩阵,java

解题思路

根据题目示例 matrix = [[1,2,3],[4,5,6],[7,8,9]] 的对应输出 [1,2,3,6,9,8,7,4,5] 可以发现,顺时针打印矩阵的顺序是 “从左向右、从上向下、从右向左、从下向上” 循环。
【算法训练-数组 三】【数组矩阵】螺旋矩阵、旋转图像、搜索二维矩阵,# 数组,算法,矩阵,java

因此,考虑设定矩阵的 “左、上、右、下” 四个边界,模拟以上矩阵遍历顺序,算法流程:

  1. 空值处理: 当 matrix 为空时,直接返回空列表 [] 即可。
  2. 初始化: 矩阵 左、右、上、下 四个边界 l , r , t , b ,用于打印的结果列表 res 。
  3. 循环打印: “从左向右、从上向下、从右向左、从下向上” 四个方向循环打印。
    • 根据边界打印,即将元素按顺序添加至列表 res 尾部。
    • 边界向内收缩 1 (代表已被打印)。
    • ** 判断边界是否相遇**(是否打印完毕),若打印完毕代表下一个方向无需打印,则跳出。
  4. 返回值: 返回 res 即可

【算法训练-数组 三】【数组矩阵】螺旋矩阵、旋转图像、搜索二维矩阵,# 数组,算法,矩阵,java
整体的打印过程
【算法训练-数组 三】【数组矩阵】螺旋矩阵、旋转图像、搜索二维矩阵,# 数组,算法,矩阵,java

代码实现

基本数据结构数组
辅助数据结构
算法
技巧

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param matrix int整型二维数组
     * @return int整型ArrayList
     */
    public ArrayList<Integer> spiralOrder (int[][] matrix) {
        // 1 入参判断,如果为空数组,返回空集合
        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 循环打印四条边
        while (true) {
            // 3-1 从左向右打印,明确左右边界,打印完后上边界向下移动,并判断是否有必要继续从上到下打印
            for (int i = left; i <= right; i++) {
                result.add(matrix[top][i]);
            }
            if (++top > bottom) {
                break;
            }

            // 3-2 从上向下打印,明确上下边界,打印完后右边界向左移动,并判断是否有必要继续从右到左打印
            for (int i = top; i <= bottom; i++) {
                result.add(matrix[i][right]);
            }
            if (left > --right) {
                break;
            }

            // 3-3 从右向左打印,明确左右边界,打印完后下边界向上移动,并判断是否有必要继续从下到上打印
            for (int i = right; i >= left; i--) {
                result.add(matrix[bottom][i]);
            }
            if (top > --bottom) {
                break;
            }

            // 3-4 从下向上打印,明确上下边界,打印完后左边界向右移动,并判断是否有必要继续从左到右打印
            for (int i = bottom; i >= top; i--) {
                result.add(matrix[i][left]);
            }
            if (++left > right) {
                break;
            }
        }

        return result;
    }
}

++top > bottom 等价于先给 top 自增 1 ,再判断++top > bottom 逻辑表达式

复杂度分析

  • 时间复杂度 O(MN) : M,N分别为矩阵行数和列数。
  • 空间复杂度 O(1) : 四个边界 l , r , t , b 使用常数大小的额外空间。

旋转图像

和螺旋矩阵类似,也是对一圈数值做处理

题干

【算法训练-数组 三】【数组矩阵】螺旋矩阵、旋转图像、搜索二维矩阵,# 数组,算法,矩阵,java

解题思路

由原题知整体的旋转公式如下:
【算法训练-数组 三】【数组矩阵】螺旋矩阵、旋转图像、搜索二维矩阵,# 数组,算法,矩阵,java
如果可以使用辅助矩阵则按如下方式修改即可:

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();
        // 根据元素旋转公式,遍历修改原矩阵 matrix 的各元素
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                matrix[j][n - 1 - i] = tmp[i][j];
            }
        }
    }
}

考虑不借助辅助矩阵,通过在原矩阵中直接「原地修改」,实现空间复杂度 **O(1)**的解法。以位于矩阵四个角点的元素为例,设矩阵左上角元素 A 、右上角元素 B 、右下角元素 C 、左下角元素 D 。矩阵旋转 90º 后,相当于依次先后执行 D→A,C→D, B→C, A→B 修改元素,即如下「首尾相接」的元素旋转操作:
【算法训练-数组 三】【数组矩阵】螺旋矩阵、旋转图像、搜索二维矩阵,# 数组,算法,矩阵,java
如上图所示,由于第 1 步 D→A已经将 A覆盖(导致 A 丢失),此丢失导致最后第 4步 A→B无法赋值。为解决此问题,考虑借助一个「辅助变量 tmp」预先存储 A ,此时的旋转操作变为:
【算法训练-数组 三】【数组矩阵】螺旋矩阵、旋转图像、搜索二维矩阵,# 数组,算法,矩阵,java
如上图所示,一轮可以完成矩阵 4 个元素的旋转。因而,只要分别以矩阵左上角 1/4的各元素为起始点执行以上旋转操作,
【算法训练-数组 三】【数组矩阵】螺旋矩阵、旋转图像、搜索二维矩阵,# 数组,算法,矩阵,java

将这些元素旋转完成即完成了整个数组的旋转
【算法训练-数组 三】【数组矩阵】螺旋矩阵、旋转图像、搜索二维矩阵,# 数组,算法,矩阵,java
具体来看,当矩阵大小n为偶数时,行列均取前n/2,当矩阵大小为奇数时,行取n/2,列取(n+1)/2,因为为奇数时,中间的元素不需要旋转

代码实现

基本数据结构数组
辅助数据结构
算法
技巧

class Solution {
    public void rotate(int[][] matrix) {
        // 1 获取数组长度,依据替换顺序位置matrix[i][j]->matrix[j][n-1-i]推导出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,列取(n+1)/2 为了应对奇数长度的n
        for (int i = 0; i < n / 2; i++) {
            for (int j = 0; j < (n + 1) / 2; j++) {
                // 2-1 暂存A的位置,用来后续替换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;
            }
        }

    }
}

复杂度分析

时间复杂度 O(N*N): 其中 N 为输入矩阵的行(列)数。需要将矩阵中每个元素旋转到新的位置,即对矩阵所有元素操作一次,使用O(N*N)的时间
空间复杂度 O(1) : 临时变量 tmp使用常数大小的额外空间。值得注意,当循环中进入下轮迭代,上轮迭代初始化的 tmp占用的内存就会被自动释放,因此无累计使用空间。

搜索二维矩阵【MID】

从下题矩阵的特性入手进行查找
【算法训练-数组 三】【数组矩阵】螺旋矩阵、旋转图像、搜索二维矩阵,# 数组,算法,矩阵,java

题干

【算法训练-数组 三】【数组矩阵】螺旋矩阵、旋转图像、搜索二维矩阵,# 数组,算法,矩阵,java

解题思路

数组从左到右和从上到下都是升序的,如果从右上角出发开始遍历呢?会发现每次都是向左数字会变小,向下数字会变大,有点和二分查找树相似。二分查找树的话,是向左数字变小,向右数字变大。所以我们可以把 target 和当前值比较。

  • 如果 target 的值大于当前值,那么就向下走。
  • 如果 target 的值小于当前值,那么就向左走。
  • 如果相等的话,直接返回 true 。

也可以换个角度思考

  • 如果 target 的值大于当前值,也就意味着当前值所在的行肯定不会存在 target 了,可以把当前行去掉,从新的右上角的值开始遍历。
  • 如果 target 的值小于当前值,也就意味着当前值所在的列肯定不会存在 target 了,可以把当前列去掉,从新的右上角的值开始遍历。

看下边的例子

[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 开始遍历, cur = 15
    
target < 15, 去掉当前列, cur = 11
[1,   4,  7, 11],
[2,   5,  8, 12],
[3,   6,  9, 16],
[10, 13, 14, 17],
[18, 21, 23, 26]    
    
target < 11, 去掉当前列, cur = 7  
[1,   4,  7],
[2,   5,  8],
[3,   6,  9],
[10, 13, 14],
[18, 21, 23]     

target > 7, 去掉当前行, cur = 8   
[2,   5,  8],
[3,   6,  9],
[10, 13, 14],
[18, 21, 23]       

target > 8, 去掉当前行, cur = 9, 遍历结束    
[3,   6,  9],
[10, 13, 14],
[18, 21, 23]   

代码实现

基本数据结构数组
辅助数据结构
算法
技巧

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param target int整型
     * @param array int整型二维数组
     * @return bool布尔型
     */
    public boolean Find (int target, int[][] array) {
        // 1 入参判断
        if (array.length < 1) {
            return false;
        }
        // 2 定义行列边界,从右上角出发,所以初始化为右上角位置
        int right = array[0].length - 1;
        int top = 0;

        // 3 出发开始遍历,明确左右边界的范围
        while (right >= 0 && top <= array.length - 1) {
            int curValue = array[top][right];
            if (curValue > target) {
                // 3-1 如果当前值大于目标值,舍弃本列
                right--;
            } else if (curValue < target) {
                // 3-2 如果当前值小于目标值,舍弃本行
                top++;
            } else {
                // 3-3 如果当前值等于目标值,找到了目标值
                return true;
            }

        }
        return false;
    }
}

复杂度分析

  • 时间复杂度 O(M+N) : 只遍历了一遍
  • 空间复杂度 O(1) :没有使用额外空间。

拓展知识:二维数组

二维数组是一种常见的数据结构,它由多行和多列组成,可以用来存储和处理二维数据集合,例如矩阵、表格、图像、地图等。在不同的编程语言中,定义和使用二维数组的方式可能有所不同,以下是一些常见编程语言中的示例。

C/C++:

// 定义一个3x3的整数二维数组
int matrix[3][3] = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};

// 访问元素
int element = matrix[1][2]; // 获取第二行第三列的元素,值为6

Python:

# 定义一个3x3的整数二维数组(使用嵌套列表)
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

# 访问元素
element = matrix[1][2] # 获取第二行第三列的元素,值为6

Java:

// 定义一个3x3的整数二维数组
int[][] matrix = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};

// 访问元素
int element = matrix[1][2]; // 获取第二行第三列的元素,值为6

常用方法和操作:

  1. 访问元素: 使用索引来访问二维数组中的特定元素,例如 matrix[i][j],其中 i 表示行号,j 表示列号。

  2. 遍历二维数组: 使用嵌套循环来遍历二维数组,通常使用一个循环迭代行,另一个循环迭代列,以访问所有元素。

  3. 初始化: 在定义二维数组时,可以初始化数组的值。可以使用嵌套列表(Python)、嵌套数组(C/C++)或类似方式来初始化。

  4. 修改元素: 可以通过索引来修改特定元素的值,例如 matrix[i][j] = newValue

  5. 获取数组的行数和列数: 可以使用数组的长度或大小来获取行数和列数。

  6. 在算法中使用: 二维数组在解决各种问题时非常有用,例如矩阵运算图算法迷宫求解等。

  7. 释放内存(C/C++): 在使用动态分配内存创建二维数组时,需要谨慎释放内存以防止内存泄漏。

二维数组是一种非常灵活和强大的数据结构,可以在各种应用中发挥作用,从简单的数据存储到复杂的算法实现。文章来源地址https://www.toymoban.com/news/detail-735390.html

到了这里,关于【算法训练-数组 三】【数组矩阵】螺旋矩阵、旋转图像、搜索二维矩阵的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C语言例题(二维数组)【转置矩阵】【成绩登记】【斐波那契】【简单矩阵查找】【螺旋数阵】【一维数组转二维数组】

    例一:转置矩阵 程序: 输出:通过b[j][i] = a[i][j];这一步实现了转置 进阶:用6个1~20内的随机数按行的顺序生成一个a[2][3]的矩阵,并输出它的转置矩阵 输出: 例2.登记某班三人的数学、英语两门课程的成绩。 分析:此类问题可以通过使用3个一维数组来解决,也可以通过使用

    2024年02月03日
    浏览(42)
  • 算法刷题-数组-螺旋矩阵

    力扣题目链接 给定一个正整数 n,生成一个包含 1 到 n^2 所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。 示例: 输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ] 这道题目可以说在面试中出现频率较高的题目, 本题并不涉及到什么算法,就是模拟过程,但却十分考察对代

    2024年02月08日
    浏览(52)
  • LeetCode-74. 搜索二维矩阵【数组 二分查找 矩阵】

    给你一个满足下述两条属性的 m x n 整数矩阵: 每行中的整数从左到右按非严格递增顺序排列。 每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target ,如果 target 在矩阵中,返回 true ;否则,返回 false 。 示例 1: 输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]],

    2024年04月14日
    浏览(41)
  • 【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值

    《博主简介》 小伙伴们好,我是阿旭。专注于人工智能AI、python、计算机视觉相关分享研究。 ✌ 更多学习资源,可关注公-仲-hao:【阿旭算法与机器学习】,共同学习交流~ 👍 感谢小伙伴 们点赞、关注! class   Solution :      def   mySqrt ( self ,  x :   int )   -   int :       

    2024年02月04日
    浏览(63)
  • 算法-有序数组的平方,长度最小的子数组,螺旋矩阵II

    伪装成一个老手! 题目 给你一个按 非递减顺序 排序的整数数组 nums,返回每个数字的平方组成的新数组,要求也按非递减顺序排序。 示例 : 输入:nums = [-4,-1,0,3,10] 输出:[0,1,9,16,100] 解释:平方后,数组变为 [16,1,0,9,100] 排序后,数组变为 [0,1,9,16,100] 来源:力扣977 思路 遍

    2024年02月11日
    浏览(41)
  • LeetCode-48. 旋转图像【数组 数学 矩阵】

    给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。 你必须在 原地 旋转图像,这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。 示例 1: 输入:matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出:[[7,4,1],[8,5,2],[9,6,3]] 示例 2: 输入:m

    2024年04月27日
    浏览(35)
  • 【算法训练-数组 五】【二分查找】:旋转排序数组的最小数字、旋转排序数组的指定数字

    废话不多说,喊一句号子鼓励自己:程序员永不失业,程序员走向架构!本篇Blog的主题是【数组的二分查找】,使用【数组】这个基本的数据结构来实现,这个高频题的站点是: CodeTop ,筛选条件为: 目标公司+最近一年+出现频率排序 ,由高到低的去 牛客TOP101 去找,只有两

    2024年02月09日
    浏览(50)
  • 【算法Hot100系列】搜索旋转排序数组

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年01月21日
    浏览(55)
  • C/C++每日一练(20230221) 格雷编码、矩阵问题、搜索旋转排序数组II

    目录 1. 格雷编码 2. 矩阵问题 3. 搜索旋转排序数组 II 格雷编码是一个二进制数字系统,在该系统中,两个连续的数值仅有一个位数的差异。 给定一个代表编码总位数的非负整数  n ,打印其格雷编码序列。即使有多个不同答案,你也只需要返回其中一种。 格雷编码序列必须

    2024年02月16日
    浏览(52)
  • 螺旋矩阵、旋转矩阵、矩阵Z字打印

    类似于这个螺旋矩阵我们也是在每次处理最外层的矩形,然后往内收缩。 对于一个矩形我们选取四个点依次进行交换即可 也是和螺旋矩阵类似选取两个点进行循环

    2024年02月10日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包