二维数组的总结

一、时间复杂度和空间复杂度

  时间复杂度和空间复杂度是衡量算法效率的两个重要指标。时间复杂度是指算法执行所需的时间，而空间复杂度是指算法执行所需的内存空间。

  计算时间复杂度和空间复杂度需要分析算法中各个操作的执行次数和内存使用情况。具体的计算方法可以根据算法的具体实现来确定，但一般情况下可以采用以下步骤：
（1）确定算法的基本操作：对于一个算法，我们需要先确定其基本操作，即算法的基本执行单元，例如赋值操作、比较操作、循环操作等。
（2）分析算法的执行次数：对于每个基本操作，我们需要分析其在算法中的执行次数，然后将这些操作的执行次数相加，得到算法的总执行次数。通常使用大O符号表示算法的时间复杂度。
（3）评估算法的空间复杂度：对于算法的内存使用情况，我们需要分析算法中所使用的数据结构、变量和递归等情况，然后评估算法的空间复杂度。同样也可以使用大O符号表示算法的空间复杂度。

二、二维数组简介

  二维数组是一种结构较为特殊的数组，只是将数组中的每个元素变成了一维数组。所以二维数组的本质上仍然是一个一维数组，内部的一维数组仍然从索引 0 开始，我们可以将它看作一个矩阵，并处理矩阵的相关问题。

  注意，实际数组中的元素由于类型的不同会占用不同的字节数，因此每个方格地址之间的差值可能不为 1。实际题目中，往往使用二维数组处理矩阵类相关问题，包括矩阵旋转、对角线遍历，以及对子矩阵的操作等。

三、旋转矩阵

在这里插入图片描述
在这里插入图片描述

解法1：使用辅助数组

在这里插入图片描述
在这里插入图片描述
c

void rotate(int** matrix, int matrixSize, int* matrixColSize) {
    int matrix_new[matrixSize][matrixSize];
    for (int i = 0; i < matrixSize; i++) {
        for (int j = 0; j < matrixSize; j++) {
            matrix_new[i][j] = matrix[i][j];
        }
    }
    for (int i = 0; i < matrixSize; ++i) {
        for (int j = 0; j < matrixSize; ++j) {
            matrix[j][matrixSize - i - 1] = matrix_new[i][j];
        }
    }
}

c++

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        // C++ 这里的 = 拷贝是值拷贝，会得到一个新的数组
        auto matrix_new = matrix;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                matrix_new[j][n - i - 1] = matrix[i][j];
            }
        }
        // 这里也是值拷贝
        matrix = matrix_new;
    }
};

解法2：原地旋转

在这里插入图片描述在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
c:

void rotate(int** matrix, int matrixSize, int* matrixColSize) {
    for (int i = 0; i < matrixSize / 2; ++i) {
        for (int j = 0; j < (matrixSize + 1) / 2; ++j) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[matrixSize - j - 1][i];
            matrix[matrixSize - j - 1][i] = matrix[matrixSize - i - 1][matrixSize - j - 1];
            matrix[matrixSize - i - 1][matrixSize - j - 1] = matrix[j][matrixSize - i - 1];
            matrix[j][matrixSize - i - 1] = temp;
        }
    }
}

c++

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < (n + 1) / 2; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - j - 1][i];
                matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
                matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
                matrix[j][n - i - 1] = temp;
            }
        }
    }
};

解法3：用翻转代替旋转

在这里插入图片描述
c

void swap(int* a, int* b) {
    int t = *a;
    *a = *b, *b = t;
}

void rotate(int** matrix, int matrixSize, int* matrixColSize) {
    // 水平翻转
    for (int i = 0; i < matrixSize / 2; ++i) {
        for (int j = 0; j < matrixSize; ++j) {
            swap(&matrix[i][j], &matrix[matrixSize - i - 1][j]);
        }
    }
    // 主对角线翻转
    for (int i = 0; i < matrixSize; ++i) {
        for (int j = 0; j < i; ++j) {
            swap(&matrix[i][j], &matrix[j][i]);
        }
    }
}

c++

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        // 水平翻转
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < n; ++j) {
                swap(matrix[i][j], matrix[n - i - 1][j]);
            }
        }
        // 主对角线翻转
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                swap(matrix[i][j], matrix[j][i]);
            }
        }
    }
};

四、零矩阵

问题：
在这里插入图片描述

解法1：使用标记数组

在这里插入图片描述
c++:

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<int> row(m), col(n);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!matrix[i][j]) {
                    row[i] = col[j] = true;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (row[i] || col[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
};

c:

void setZeroes(int** matrix, int matrixSize, int* matrixColSize) {
    int m = matrixSize;
    int n = matrixColSize[0];
    int row[m], col[n];
    memset(row, 0, sizeof(row));
    memset(col, 0, sizeof(col));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (!matrix[i][j]) {
                row[i] = col[j] = true;
            }
        }
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (row[i] || col[j]) {
                matrix[i][j] = 0;
            }
        }
    }
}

解法2：使用两个标记变量

在这里插入图片描述
c++

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        int flag_col0 = false, flag_row0 = false;
        for (int i = 0; i < m; i++) {
            if (!matrix[i][0]) {
                flag_col0 = true;
            }
        }
        for (int j = 0; j < n; j++) {
            if (!matrix[0][j]) {
                flag_row0 = true;
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (!matrix[i][j]) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (!matrix[i][0] || !matrix[0][j]) {
                    matrix[i][j] = 0;
                }
            }
        }
        if (flag_col0) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
        if (flag_row0) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }
    }
};

c

void setZeroes(int** matrix, int matrixSize, int* matrixColSize) {
    int m = matrixSize;
    int n = matrixColSize[0];
    int flag_col0 = false, flag_row0 = false;
    for (int i = 0; i < m; i++) {
        if (!matrix[i][0]) {
            flag_col0 = true;
        }
    }
    for (int j = 0; j < n; j++) {
        if (!matrix[0][j]) {
            flag_row0 = true;
        }
    }
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (!matrix[i][j]) {
                matrix[i][0] = matrix[0][j] = 0;
            }
        }
    }
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (!matrix[i][0] || !matrix[0][j]) {
                matrix[i][j] = 0;
            }
        }
    }
    if (flag_col0) {
        for (int i = 0; i < m; i++) {
            matrix[i][0] = 0;
        }
    }
    if (flag_row0) {
        for (int j = 0; j < n; j++) {
            matrix[0][j] = 0;
        }
    }
}

解法3:使用一个标记向量

在这里插入图片描述
c++

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        int flag_col0 = false;
        for (int i = 0; i < m; i++) {
            if (!matrix[i][0]) {
                flag_col0 = true;
            }
            for (int j = 1; j < n; j++) {
                if (!matrix[i][j]) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        for (int i = m - 1; i >= 0; i--) {
            for (int j = 1; j < n; j++) {
                if (!matrix[i][0] || !matrix[0][j]) {
                    matrix[i][j] = 0;
                }
            }
            if (flag_col0) {
                matrix[i][0] = 0;
            }
        }
    }
};

c

void setZeroes(int** matrix, int matrixSize, int* matrixColSize) {
    int m = matrixSize;
    int n = matrixColSize[0];
    int flag_col0 = false;
    for (int i = 0; i < m; i++) {
        if (!matrix[i][0]) {
            flag_col0 = true;
        }
        for (int j = 1; j < n; j++) {
            if (!matrix[i][j]) {
                matrix[i][0] = matrix[0][j] = 0;
            }
        }
    }
    for (int i = m - 1; i >= 0; i--) {
        for (int j = 1; j < n; j++) {
            if (!matrix[i][0] || !matrix[0][j]) {
                matrix[i][j] = 0;
            }
        }
        if (flag_col0) {
            matrix[i][0] = 0;
        }
    }
}

五、对角线遍历

在这里插入图片描述

解法：直接模拟

在这里插入图片描述
c:

int* findDiagonalOrder(int** mat, int matSize, int* matnSize, int* returnSize) {
    int m = matSize;
    int n = matnSize[0];
    int *res = (int *)malloc(sizeof(int) * m * n);
    int pos = 0;
    for (int i = 0; i < m + n - 1; i++) {
        if (i % 2) {
            int x = i < n ? 0 : i - n + 1;
            int y = i < n ? i : n - 1;
            while (x < m && y >= 0) {
                res[pos] = mat[x][y];
                pos++;
                x++;
                y--;
            }
        } else {
            int x = i < m ? i : m - 1;
            int y = i < m ? 0 : i - m + 1;
            while (x >= 0 && y < n) {
                res[pos] = mat[x][y];
                pos++;
                x--;
                y++;
            }
        }
    }
    *returnSize = m * n;
    return res;
}

c++

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
        int m = mat.size();
        int n = mat[0].size();
        vector<int> res;
        for (int i = 0; i < m + n - 1; i++) {
            if (i % 2) {
                int x = i < n ? 0 : i - n + 1;
                int y = i < n ? i : n - 1;
                while (x < m && y >= 0) {
                    res.emplace_back(mat[x][y]);
                    x++;
                    y--;
                }
            } else {
                int x = i < m ? i : m - 1;
                int y = i < m ? 0 : i - m + 1;
                while (x >= 0 && y < n) {
                    res.emplace_back(mat[x][y]);
                    x--;
                    y++;
                }
            }
        }
        return res;
    }
};

代码解析
这行代码使用了 emplace_back() 函数将一个元素添加到名为 res 的容器的末尾。被添加的元素是二维数组或矩阵 mat 在位置 (x, y) 处的元素 mat[x][y]。

emplace_back() 函数是 C++ 中 std::vector 类的一个成员函数，它可以在容器的末尾直接构造对象。这意味着它可以直接在容器的内存中构造对象，而不需要进行复制或移动操作。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/12976.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

亚马逊、ebay、temu如何提升产品点击率？测评自养号解析

亚马逊、ebay、temu如何提升产品点击率？测评自养号解析

产品点击率对于店铺销售额的影响至关重要&#xff0c;尤其是在竞争越来越激烈的市场环境中&#xff0c;想要有销量和转化&#xff0c;提高产品listing点击率成为了非常关键的一环。 1. 产品主图 顾客浏览产品时&#xff0c;第一眼看到的就是主图&#xff0c;一张优质的主图更容…
阅读更多...
CSDN博客编写教程

CSDN博客编写教程

这里写自定义目录标题 欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题&#xff0c;有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants 创建一个自定义列表如何创建一个…
阅读更多...
UniLM模型简单介绍

UniLM模型简单介绍

目录 一、概要 二、深入扩展 2.1 预训练任务 2.2 模型精调 一、概要 如果将基于Transformer的双向语言模型&#xff08;如BERT模型中的掩码语言模型&#xff09;与单向的自回归语言模型&#xff08;如BART模型的解码器&#xff09;进行对比&#xff0c;可以发现&#xff0c…
阅读更多...
springboot+vue职称评审管理系统（源码+文档）

springboot+vue职称评审管理系统（源码+文档）

风定落花生&#xff0c;歌声逐流水&#xff0c;大家好我是风歌&#xff0c;混迹在java圈的辛苦码农。今天要和大家聊的是一款基于springboot的职称评审管理系统。项目源码请联系风歌&#xff0c;文末附上联系信息 。 目前有各类成品java毕设&#xff0c;需要请看文末联系方式 …
阅读更多...
[Java]监听器（Listener）

[Java]监听器（Listener）

过滤器&#xff08;Filter&#xff09;https://blog.csdn.net/m0_71229255/article/details/130246404?spm1001.2014.3001.5501 一 : Listener监听器简述 监听器就是监听某个对象的的状态变化的组件 监听器的相关概念&#xff1a; 事件源&#xff1a; 被监听的对象 ----- 三…
阅读更多...
（补）4.13每日一题

（补）4.13每日一题

给定一个字符串 s &#xff0c;请你找出其中不含有重复字符的 最长子串 的长度。 题目连接&#xff1a;https://leetcode.cn/problems/longest-substring-without-repeating-characters/ 解题 开始我把这个题目想简单了&#xff0c;我想的是输入一个字符串&#xff0c;从第一…
阅读更多...
【系统集成项目管理工程师】项目整体管理

【系统集成项目管理工程师】项目整体管理

&#x1f4a5;十大知识领域&#xff1a;项目整体管理 项目整体管理包括以下 6 个过程: 制定项目章程定项目管理计划指导与管理项目工作监控项目工作实施整体变更控制结束项目或阶段过程 一、制定项目章程 制定项目章程。编写一份正式文件的过程&#xff0c;这份文件就是项目章程…
阅读更多...
pushmall推贴共享电商2023年4月计划

pushmall推贴共享电商2023年4月计划

Pushmall推贴共享电商2023年4月计划 2023年 二月份优化完成 1、商圈套餐卡&#xff1a;商品、优惠券、活动优化&#xff1b; 2、会员预充值一卡通&#xff1a;指定商家会员卡充值优惠&#xff1b; 3、商家海报&#xff1a;店铺海报、商品海报、商圈卡海报优化。 4、首页重新布…
阅读更多...
MLCC周期性分析：当前时点处于周期反转前夜

MLCC周期性分析：当前时点处于周期反转前夜

MLCC是电子工业大米&#xff0c;供需波动导致行业成周期性波动 MLCC是最常用的被动元器件之一&#xff0c;终端下游涵盖消费电子、家电、汽车、通信等。在5g、汽车电子、智能硬件的推动下&#xff0c;MLCC行业需求稳步增长。供给端来看&#xff0c;中国大陆厂商合计市场份额不…
阅读更多...
数据要素化全面提速，数据复制将迎来春天？

数据要素化全面提速，数据复制将迎来春天？

数据复制市场将迎来真正的春天&#xff1f; 目前看的确如此。近日&#xff0c;国家发改委密集发文&#xff0c;从产权、分配、流通、安全等多个角度解读“数据二十条”&#xff08; 《中共中央国务院关于构建数据基础制度更好发挥数据要素作用的意见》&#xff0c;简称“数据二…
阅读更多...
Bots攻击威胁石油石化企业 瑞数动态安全实现从“人防”到“技防”

Bots攻击威胁石油石化企业 瑞数动态安全实现从“人防”到“技防”

近日&#xff0c;中国石油石化企业信息技术交流大会暨油气产业数字化转型高峰论坛在京召开。本届大会由中国石油学会、中国石油、中国石化、中国海油、国家管网、国家能源、中国中化、中国航油、延长石油、中国地质调查局等单位共同主办。 作为我国石油石化行业的盛会&#xf…
阅读更多...
什么是设计模式？

什么是设计模式？

目录 常见的设计模式 创建型模式 结构型模式 行为型模式 总结 设计模式&#xff08;Design Pattern&#xff09;是一些被认为是最佳实践的面向对象编程经验的总结&#xff0c;它们提供了解决特定场景问题的可复用方案。设计模式可以加速开发过程并提高代码质量和可读性&…
阅读更多...
GFD233A 3BHE022294R0103

GFD233A 3BHE022294R0103

GFD233A 3BHE022294R0103 ABB KUC321AE PLC模块 HIEE300698R0001 KU C321 AE01 ABB KUC711 3BHB004661R0001 高压变频模块 KUC711AE ABB KUC755AE105 3BHB005243R0105 驱动控制系统模块 KUC755 ABB KUC755AE106 3BH005243R006 控制系统模块 KU C755 AE 106 ABB LDGRB-01 3BSE01…
阅读更多...
【C语言】基础语法1：变量和数据类型

【C语言】基础语法1：变量和数据类型

下一篇&#xff1a;运算符和表达式 ❤️‍&#x1f525;前情提要❤️‍&#x1f525;   欢迎来到C语言基本语法教程   在本专栏结束后会将所有内容整理成思维导图&#xff08;结束换链接&#xff09;并免费提供给大家学习&#xff0c;希望大家纠错指正。本专栏将以基础出发…
阅读更多...
知乎版ChatGPT「知海图AI」加入国产大模型乱斗，称效果与GPT-4持平

知乎版ChatGPT「知海图AI」加入国产大模型乱斗，称效果与GPT-4持平

“2023知乎发现大会”上&#xff0c;知乎创始人、董事长兼CEO周源和知乎合作人、CTO李大海共同宣布了知乎与面壁智能联合发布“知海图AI”中文大模型。 周源据介绍&#xff0c;知乎与面壁智能达成深度合作&#xff0c;共同开发中文大模型产品并推进应用落地。目前&#xff0c;知…
阅读更多...
vue 报错 error:03000086:digital envelope routines::initialization error解决方案

vue 报错 error:03000086:digital envelope routines::initialization error解决方案

目录 1. 引言: 2. 更换版本出现问题: 3. 出现原因: 4. 解决办法: -> 4. 1 删了 再换回16.15版本 -> 4.2 指令修改(好使) ---> 4.2.1效果如图 -> 4.3 其他指令就别试了 压根不好使 1. 引言: npm出现问题 , 卸载后 装了个新node 18.15版本 2. 更换版本…
阅读更多...
JavaScript【三】JavaScript中的数组

JavaScript【三】JavaScript中的数组

文章目录 &#x1f31f;前言&#x1f31f;数组&#x1f31f;声明&#xff1a;&#x1f31f; 隐式创建&#xff1a;&#x1f31f; 实例化构造函数&#xff1a; &#x1f31f; 注意&#xff1a;一个值为数组的长度。&#x1f31f; 访问&#xff1a;&#x1f31f; 遍历&#xff1a…
阅读更多...
SpringCloud+RabbitMQ+Docker+Redis+搜索+分布式，系统详解springcloud微服务技术栈（Eureka、Ribbon）

SpringCloud+RabbitMQ+Docker+Redis+搜索+分布式，系统详解springcloud微服务技术栈（Eureka、Ribbon）

微服务技术栈导学 微服务技术是分布式架构&#xff08;把服务做拆分&#xff09;的一种 而springcloud仅仅是解决了拆分时的微服务治理的问题&#xff0c;其他更复杂的问题并没有给出解决方案 一个完整的微服务技术要包含的不仅仅是springcloud 微服务技术栈 包括什么 …
阅读更多...
深度学习中的各种不变性

深度学习中的各种不变性

不变性 平移不变性&#xff08;Translation Invariance&#xff09;旋转不变性&#xff08;Ratation Invariance&#xff09;尺度不变性&#xff08;Size Invariance&#xff09;光照不变性&#xff08;Illumination Invariance&#xff09;仿射不变性&#xff08;Affine Invar…
阅读更多...
springcloud2.1.0整合seata1.5.2+nacos2.10（附源码）

springcloud2.1.0整合seata1.5.2+nacos2.10（附源码）

springcloud2.1.0整合seata1.5.2nacos2.10&#xff08;附源码&#xff09; 1.创建springboot2.2.2springcloud2.1.0的maven父子工程如下&#xff0c;不过多描述&#xff1a; 搭建过程中也出现很多问题&#xff0c;主要包括&#xff1a; 1.seataServer.properties配置文件的组…
阅读更多...
最新文章

Copyright @ 2022~2023