有序数组的平方题目如下:
如果是可以使用O(nlogn)或以上复杂度的算法,本题可以简单的先平方一遍,然后使用排序算法就可以了
但是要求使用O(n)复杂度的算法,那么我首先想到的是昨天的快慢指针类似的想法:
我想先平方一次数组,然后从中间开始排序,如下
但是运行之后发现从中间开始进行相邻元素的比较好像很难达到O(n)的复杂度,开始卡壳
看了题解思路发现我的解法正好相反,其实这个数组给的是一个有序的数组,那么他的平方最大值应该是在两边出现,那么
两个指针从两边向中间靠拢指针直接互相比较就可以获得有序数组了,而如果从中间比较,我们没办法知道最小值的具体位置,
而且随着数组的元素个数是奇数还是偶数也会发生一定的变化,更极端的,如果数组只有一个负数和一万个正数,那么最小值
将在左端出现而不是中间,大大增加了比较的难度,也就达不到O(n)的时间复杂度
对vector容器有点不熟悉,没有确定容量报了一下数组空间的问题
规范化初始vector后问题迎刃而解
寻找长度最小的子数组题目如下:
对于O(n)级别的算法 没什么思路 想到有点类似动态规划但又不太一样 只能先看看视频的思路讲解 再尝试
第一次尝试判断写了if 错了
应该是写成while 如果写的是if 那么满足条件窗口的右端就会继续划 窗口长度都不会改变
最小的窗口肯定找不到
个人解法如下:
其实后面一个for可以省去,只要赋值一个特别大的值,做完算法之后看看这个值有没有被修改就行了
螺旋矩阵题目:
螺旋矩阵完全没有接触过 没有一点思路
看了视频之后有点想太多 难点不在于算法而是边界的上的处理
这里我的解法统一使用offset来表示每圈的起始坐标
写的时候笨比了一下 直接while条件写成了 n /2 每圈还要--的 得再开个变量
标签:02,窗口,矩阵,复杂度,随想录,算法,数组,day,指针 From: https://www.cnblogs.com/mingtiao/p/17932469.html