【算法-数组3】螺旋数组(一入循环深似海啊!)

这篇具有很好参考价值的文章主要介绍了【算法-数组3】螺旋数组(一入循环深似海啊!)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

今天,带来数组相关算法的讲解。文中不足错漏之处望请斧正!

理论基础点这里


螺旋数组

1. 思路

这道题主要是模拟转圈过程,但是要处理的边界条件比较多,常见的问题就是每条边的处理都有自己的逻辑,那这就很难。如果不明确每条边该如何遍历,比如当n=5,上行填充5个元素,但是右列又只填充4个元素——每条边的区间不统一,就导致旋转起来很困难。即使第一圈转完了,第二圈也不知道如何向内走。

在二分搜索的时候,我们讲过循环不变量,这里也可以用上,来使循环变得清晰。

我们这里对每条边的处理,采用左闭右开的规则,即左闭右开的处理边界是循环不变量。
同时,我们对整个螺旋矩阵的生成拆分一下:

  • 螺旋矩阵 = 按顺时针顺序旋转的一圈一圈递增的数字
  • 每圈数字 = 上行(从左到右)的填充 + 右列(从上到下)的填充 + 下行(从右到左)的填充 + 左列(从下到上)的填充

【算法-数组3】螺旋数组(一入循环深似海啊!),算法,算法
如图中一样,将目标矩阵拆分,最终只需要重复最简单的“右上左下填充操作”就可以生成目标矩阵。

具体怎么走呢?

*我们表示元素的时候一般是nums[i][j],i表示行的位置,j表示列的位置,所以等会遍历某一行的时候,元素nums[i][j]的列(j)在变化,循环变量用j;遍历某一列的时候,元素nums[i][j]的行(i)在变化,循环变量用i。

startI代表行的起始位置,startJ代表列的起始位置,则

  • 上行(遍历行,元素的列在变化):j: [startJ -> n-1);
  • 右列(遍历列,元素的行在变化):i: [startI -> n-1);
    【算法-数组3】螺旋数组(一入循环深似海啊!),算法,算法
    图中:
  • startI = 0
  • startJ = 0
  • j: [startJ, n-1)
  • i: [startI, n-1)

  • 下行(遍历行,元素的列在变化):j: [j -> startJ)
    • 由于向右走完,j已经为n-1,所以可以直接从j开始
  • 左列(遍历列,元素的行在变化):i: [i -> startI)
    • 由于向下走完,i已经为n-1,所以可以直接从i开始

【算法-数组3】螺旋数组(一入循环深似海啊!),算法,算法
图中:

  • startI = 0
  • startJ = 0
  • i= n-1
  • j= n-1
  • j: [n-1, startJ)
  • i: [n-1, startI)

最外一圈走完了,那怎么往里面走呢?

其实只需要稍稍改动:走完一圈,要转的圈就缩小了,即下一圈的行是[startJ+1, n-2),列同理。

左区间很简单,边转圈边增加startIstartJ,那右区间呢?不如我们直接默认给一个值为 n-1 的eleNum变量, 表示每次要填充的元素个数.

那我们转几圈呢?

n/2圈。因为每次转弯一圈,都是向最左列最右列、最上行最下行放置了元素。

那如果n是奇数呢?

就像我们图中画的一样,最后会剩下一个,我们在结尾特殊处理即可。

2. 参考代码

class Solution {
public:
    // 循环进行右下左上的填充操作
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> matrix(n, vector<int>(n, 0));

        // 关于行列:
        // 1. 遍历行, 列属性变化 -- j移动
        // 2. 遍历列, 行属性变化 -- i移动
        int startI = 0; // i起始位置
        int startJ = 0; // j起始位置
        int eleNum = n - 1; // 每次要填充的元素个数
        int loopNum = n / 2; // 循环次数(奇数需要单独处理最后一个元素)
        int val = 1; // 要填充的值

        while (loopNum--) {
            int i = startI; // 某元素的行属性
            int j = startJ; // 某元素的列属性

            // 从左到右遍历行(列属性变化 -- j移动)
            for (j = startJ; j < eleNum; ++j) matrix[i][j] = val++;

            // 从上到下遍历列(行属性变化 -- i移动)
            for (i = startI; i < eleNum; ++i) matrix[i][j] = val++;

            // 从右到左遍历行(列属性变化 -- j移动)
            for (; j > startJ; --j) matrix[i][j] = val++;

            // 从下到上遍历列(行属性变化 -- i移动)
            for (; i > startI; --i) matrix[i][j] = val++;

            // 每次循环后, 需要填充的区间左右同时向中间缩一位
            // 行: [startJ, eleNum) --> [startJ+1, eleNum-1)
            // 列: [startI, eleNum) --> [startI+1, eleNum-1)
            ++startI;
            ++startJ;
            --eleNum; 
        }

        //  当 n 为奇数, 矩形中间会留下一个没处理的
        if (n % 2 != 0) matrix[n / 2][n / 2] = val;

        return matrix;
    }
};

今天的分享就到这里了,感谢您能看到这里。

这里是培根的blog,期待与你共同进步!文章来源地址https://www.toymoban.com/news/detail-745329.html

到了这里,关于【算法-数组3】螺旋数组(一入循环深似海啊!)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 算法-有序数组的平方,长度最小的子数组,螺旋矩阵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)
  • 算法训练第二天|977.有序数组的平方、209.长度最小的有序数组、59.螺旋矩阵2

    题目链接:力扣 思路:同样使用双指针的方法,这样就可以只遍历一次原数组。 可以考虑需要按照一个顺序来遍历,那就是从大到小或者从小到大,我选择的是从大到小。 不难看出,原数组将每个数平方后,呈现从两边到中间逐渐减小的规律。 所以使用一个指针指向原数组

    2023年04月22日
    浏览(54)
  • 算法训练 Day 2 | 数组:977.有序数组的平方,209.长度最小的子数组,59.螺旋矩阵II

    977. 有序数组的平方 第一想法:暴力破解 看完题解想法:朝着双指针方向想 遇到困难: 用双指针的话,一开始想到两边指针往中间靠,逐个将最大值赋给结果数组。和题解不同的是,循环条件我写了  while (left != right) {...} ,相比于题解的  while (left = right) {...} ,我需要在后

    2023年04月12日
    浏览(41)
  • 算法:轮转数组---循环取模运算

    1、题目: 给定一个整数数组 nums,将数组中的元素向右轮转 k 个位置,其中 k 是非负数。 2、 分析特点: 轮转 == 取模运算 我们可以使用额外的数组来将每个元素放至正确的位置。用 n 表示数组的长度,我们遍历原数组,将原数组下标为 i 的元素放至新数组下标为 (i+k) mo

    2024年02月09日
    浏览(38)
  • 【剑指offer|图解|数组】寻找文件副本 + 螺旋遍历二维数组

    🌈个人主页: 聆风吟 🔥系列专栏: 数据结构、剑指offer每日一练 🔖少年有梦不应止于心动,更要付诸行动。 ⌈ 在线OJ链接,可以转至此处自行练习 ⌋ 设备中存有 n 个文件,文件 id 记于数组 documents 。若文件 id 相同,则定义为该文件存在副本。请返回任一存在副本的文件

    2024年02月05日
    浏览(38)
  • 有序数组的平方 长度最小的子数组 螺旋矩阵II

    977. 有序数组的平方 - 力扣(LeetCode) 给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。 示例 1: 输入:nums = [-4,-1,0,3,10] 输出:[0,1,9,16,100] 解释:平方后,数组变为 [16,1,0,9,100],排序后,数组变为 [0,1,9,16,100] 示例

    2024年02月12日
    浏览(44)
  • 代码随想录【数组】----->有序数组的平方、长度最小的子数组、螺旋矩阵

    题目LeetCode977. 有序数组的平方 由于平方后 两边的元素最大,中间的元素最小 ,所以可以使用双指针。 定义left指向原数组最左边,right指向原数组最右边 比较left元素的平方和right元素的平方 left元素平方大于right元素平方,将left元素平方放在结果集最后,left++ right元素平方

    2023年04月27日
    浏览(68)
  • 有序数组的平方 和 滑动窗口 和 螺旋矩阵

    leetcode 代码如下(示例): 负数的平方  是要比较小正数平方大的    可以先求出所有数的平方,在排序,较麻烦 采用双指针 头指针 i 和尾指针 j 和 记数组元素个数的 k 将  头指针  和 尾指针 所指元素 平方进行比较  较大一个放到新数组的尾部  指针减一  

    2024年02月06日
    浏览(47)
  • Day 2 数组:977.有序数组的平方 209.长度最小的子数组 59.螺旋矩阵Ⅱ

    977.有序数组的平方 题目链接 💡思路 暴力解法 将数组内每个数平方每个数平方之后,按升序排序 代码如下: 时间复杂度: O (   n l o g n ) O( nlogn) O (   n l o g n ) 空间复杂度: O ( 1 ) O(1) O ( 1 ) 时间复杂度具体分析: for循环: O(n) 快速排序 : O(nlogn) 因此时间复杂度是 O (  

    2024年02月10日
    浏览(50)
  • 有序数组的平方、长度最小的子数组、螺旋矩阵II(Day2)

    题目链接:https://leetcode.cn/problems/squares-of-a-sorted-array/ 第一反应暴力如上代码 下面写一段用双指针思想的代码 题目链接:https://leetcode.cn/problems/minimum-size-subarray-sum/ 本题暴力解法会超时,以下采用滑动窗口的方式(将暴力的两个for循环变成一个) 题目链接:https://leetcode.cn/

    2023年04月26日
    浏览(40)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包