代码随想录算法训练营第二天 |-数组篇97720959

文章目录

• • 数组977-有序数组的平方
  • • 题目&难度
    • 示例
    • 写在前面
    • 算法——暴力+快速排序&双指针法
    • • 1.暴力+快速排序
      • 2.双指针法
  • 数组209-长度最小的子数组
  • • 题目&难度
    • 示例
    • 算法——滑动窗口（双指针法）
    • 复杂度分析
  • 数组59-螺旋矩阵Ⅱ
  • • 题目
    • 示例
    • 值得注意的
    • 算法——按层模拟
    • 疑难分析
    • 算法复杂度分析

数组977-有序数组的平方

今天状态不好（叹气）。

题目&难度

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
提示：1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 已按 非递减顺序 排序

示例

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

写在前面

通读一遍题目，可以知道的是，这里的非递减排序可以解释如下：

$\forall i<j,A[i]\ge A[j]$

**快速排序：**排序算法中效率很高但不够稳定的算法，时间复杂度为 O ( log ⁡ n ) ∼ O ( n 2 ) O(\log{n}) \sim O(n^2) O(logn)∼O(n2)。

算法思想：

​ 这里其实是借用的双指针思路，一个左指针，一个右指针，两者指向边界元素；基准元素定下后，右指针先移动，左指针再移动，指针所指的数大小与基准元素比较，若是右边较基准元素小而左边较基准元素大则两者互换；如此往复，直到两指针所指位置重合结束（递归思想）。

这里参考大佬的分析过程，贼细致，认真观摩学习了。

参考文章：

https://blog.csdn.net/qq_40941722/article/details/94396010?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522168197439616800192264664%2522%252C%2522scm%2522%253A%252220140713.130102334…%2522%257D&request_id=168197439616800192264664&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2_alltop_positive~default-1-94396010-null-null.142^v85wechat,239^v2insert_chatgpt&utm_term=%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F&spm=1018.2226.3001.4187

算法——暴力+快速排序&双指针法

1.暴力+快速排序

这里就不多对暴力解法进行赘述了，上一篇博客有说了暴力解法的相关，这边既然已经分析清楚了，那就直接see see code。

这里的主函数不是leecode的标准解答里的，是我自己调试方便写的。

我个人喜欢把东西拆开揉碎了看，所以代码就没有那么酷炫，比较朴实吧（笑，耸肩），不过更多的是我不够强罢了。

#include//暴力+快排//数组自身元素求平方
int* multip(int *nums, int returnSize){int numsSize = returnSize;for(int i = 0; i < numsSize; i++)nums[i] = nums[i] * nums[i];return nums;
}//用来交换的函数
void swap(int nums[], int left, int right){int temp = nums[left];nums[left] = nums[right];nums[right] = temp;
}//分区操作
int partition(int nums[], int left, int right){//基准值,一开始选数组第0位int base = nums[left];while(left < right){//右边先走（不能调换顺序！）while(left < right && base <= nums[right]){right--;}swap(nums, left, right);//左边走while(left < right && base >= nums[left]){left++;}swap(nums, left, right);}//返回基准值的位置return left;
}//快速排序
int* quickSort(int nums[], int left, int right){if(left < right){//基准值int base = partition(nums, left, right);//递归开始//左半边排序quickSort(nums, left, base - 1);//右半边排序quickSort(nums, left+1, right);}return nums;
}int main(){int nums_[] = {5,13,6,24,2,8,19,27,6,12,1,17};//计算数组长度int numsSize = sizeof(nums_) / sizeof(int);int* nums = multip(nums_, numsSize);int *realnums = quickSort(nums, 0, numsSize - 1);for(int i = 0; i < numsSize; i++)printf("%d\n", nums[i]);return 0;
}

所得结果：

备注：现在是2023/4/20/23:26

嗯……就是用官方的函数的话不知道为什么一直不太行，所以就自己写主函数了。嗯，感觉……有空的话要好好看下这个问题。

不建议拿到力扣上运行，因为我感觉不太行。

算法复杂度分析：

时间复杂度：左右遍历为$O(n)$，而进一步递归的复杂度为 O ( log ⁡ 2 n ) O(\log_{2}{n}) O(log2​n)，两者结合为 O ( n l o g 2 n ) O(nlog_{2}{n}) O(nlog2​n)。

空间复杂度： O ( log ⁡ 2 n ) O(\log_{2}{n}) O(log2​n)，哎，这里不要看了吧，我感觉今天写的很不好。以后还要好好看下这个问题。

但是我感觉还是没有好好搞清楚这个问题，不够透彻，我觉得这里不能误导大家。

2.双指针法

来了，所谓的简便方法。

题目里说到，非降序，是升序排列的，那么经过平方后我们需要注意三种情况：

1.数组元素均为非负数，直接一路递增，很简单。

2.数组元素均为非正数，经过平方后，为降序。

3.数组里有负数：原数组元素从负数递增到正数，经过平方后需要讨论分界。

综上所述，最大值一定不在中间，而在两端。

int* sortedSquares(int* nums, int numsSize, int* returnSize){//returnSize就是返回的数组大小*returnSize = numsSize;//初始化双指针int i = 0;int j = numsSize - 1;//定义新数组resultint* result = (int *)malloc(sizeof(int) * numsSize);//指向数组末位置，让result数组逆着输出int k = numsSize - 1;while(i <= j){if(nums[i] * nums[i] > nums[j] * nums[j]){result[k] = nums[i] * nums[i];k--;i++;}else{result[k] = nums[j] * nums[j];k--;j--;}}return result;
}

时间复杂度：$O(n)$

空间复杂度：嘶……力扣说是O(1)就是O(1)了？不行，我迟早要好好研究下这两个问题。

数组209-长度最小的子数组

题目&难度

给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

难度：中等题。

示例

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

2023/4/20/23:48

受不了了，累了累了，从晚8点15一直写现在。洗漱睡觉，明天再写。

算法——滑动窗口（双指针法）

一刷和二刷的代码：

/*一刷代码-有bug
int minSubArrayLen(int target, int* nums, int numsSize){//初始化子数组起始位置i,//滑动窗口最小长度result,//滑动窗口数组元素之和sum//滑动窗口长度subLengthint result=INT_MAX;int i=0;int sum=0;int subLength=0;//滑动窗口//这里的j表示终止位置for(int j=0;j=target){subLength=j-i+1;result=fmin(result,subLength);sum=sum-nums[i];//变更滑动窗口起始位置i++;}}return result;}
*///二刷代码
int minSubArrayLen(int target, int* nums,int numsSize){//滑动窗口（双指针）标记起始位置iint i = 0;//初始化最小长度resultint result = INT_MAX;//初始化滑动窗口之和sum为0int sum = 0;//初始化滑动窗口长度int subLength = 0;//滑动窗口，终止位置为j,由j遍历一遍后面的元素for(int j = 0; j < numsSize; j++){sum += nums[j];//这里因为是滑动窗口，需要循环动作，所以必须用while不能用ifwhile(sum >= target){//表示连续子数组长度subLength = j - i + 1;result = fmin(result, subLength);//滑动窗口的关键——当sum大于目标值target则将初始位置的//值减去，然后再让i往后移动sum = sum - nums[i];i++;}}return result;
}

复杂度分析

时间复杂度：O(n)

空间复杂度：O(1)

输出结果：

无法通过的原因分析：

这是因为没有考虑当滑动窗口之和小于等于target的情况，所以当target=11时，即使滑动窗口走完也无法找到最小的长度，所以会输出INT_MAX，然而正确的情况是此时应该返回0。

关键代码为：return result == INT_MAX ? 0 : result;

代码修正后：

int minSubArrayLen(int target, int* nums,int numsSize){//滑动窗口（双指针）标记起始位置iint i = 0;//初始化最小长度resultint result = INT_MAX;//初始化滑动窗口之和sum为0int sum = 0;//初始化滑动窗口长度int subLength = 0;//滑动窗口，终止位置为j,由j遍历一遍后面的元素for(int j = 0; j < numsSize; j++){sum += nums[j];//这里因为是滑动窗口，需要循环动作，所以必须用while不能用ifwhile(sum >= target){//表示连续子数组长度subLength = j - i + 1;result = fmin(result, subLength);//滑动窗口的关键——当sum大于目标值target则将初始位置的//值减去，然后再让i往后移动sum = sum - nums[i];i++;}}return result == INT_MAX ? 0 : result;
}

此时运行成功，案例全部通过。

运行结果图：

以下是失败的提交结果统计（包含第一第二次的刷题提交）

算法复杂度分析

时间复杂度：O(n)

PS(碎碎念)：不要以为for里放一个while就以为是O(n^2)啊， 主要是看每一个元素被操作的次数，每个元素在滑动窗后进来操作一次，出去操作一次，每个元素都是被操作两次，所以时间复杂度是 2 × n 也就是O(n)。

空间复杂度：O(1)

数组59-螺旋矩阵Ⅱ

题目

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

示例

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rSEx6Y3u-1682042517335)(null)]

输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]

值得注意的

这道题需要明白的是对于边界条件的判定，如对于左闭右闭、左闭右开之类的选择。这里转圈的边界条件在于左闭右开。

比如顶上的是红色，然后留下最后一个节点给右边遍历，留下最下方的节点给地下的一条边，左边就不再读取边1的第一个，如此转圈得到外圈。

内圈的话由于外圈的缘故，因此缩进一个。

循环不变量：每条边的处理规则必须相同。

算法——按层模拟

第一次提交：

/*** Return an array of arrays of size *returnSize.* The sizes of the arrays are returned as *returnColumnSizes array.* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().*///一刷代码,有很多不明白的
int** generateMatrix(int n, int* returnSize, int** returnColumnSizes){//初始化返回的结果数组的大小*returnSize = n;//ColumnSizes的意思是指列的大小*returnColumnSizes = (int*)malloc(sizeof(int) * n);//初始化返回结果数组ans——但是这一坨代码是真不明白啊int** ans = (int**)malloc(sizeof(int) * n);for(int i = 0; i < n; i++){ans[i] = (int*)malloc(sizeof(int) * n);(*returnColumnSizes)[i] = n;}//设置每循环一个圈的起始位置int startX = 0;int startY = 0;//设置二维数组的中间的位置，当n=3那么中间的数就是(1,1)int mid = n / 2;//每个圈循环几次，如果n为奇数3，那么loop=1,只是循环一圈int loop = n / 2;//用来给矩阵中每一个空格赋值int count = 1;//每一圈循环都需要控制每一条边遍历的长度,就是与其他边对接时的右开int offset = 1;//定义行列索引int i ,j;/*这一段是外圈的顺时针遍历*/while(loop){//顶上的边遍历//n-offset为边界，表示不处理最后一个点for(j = startY; j < n - offset; j++){ans[startX][j] = count++;}//右边的边遍历for(i = startX; i < n - offset; i++){ans[i][j] = count++;}//底下的边遍历(i=2,j=2开始，因此需要让i不变，j自减)for(; j > startY; j--){ans[i][j] = count++;}//左边的边遍历（从i=2,j=0开始，此时只需要让i自减）for(; i > startX; i--){ans[i][j] = count++;}//第二圈开始时，起始位置各自＋1startX++;startY++;//此时进入内圈，所以缩进＋1offset++;}/*这里是单独给矩阵中间赋值*/if(n % 2 == 1)ans[mid][mid] = count;return ans;
}

提交结果：

内存溢出，存在数组越界的情况，于是回头复查。

错误排查

经过排查和对比，原来是offset应该自加2，因为是偶数圈；以及loop应该自减1，因为圈数减少了。

但是还是有错，继续排查。

把代码又改了好几个地方，但是还是报错，是为啥呢？

/*** Return an array of arrays of size *returnSize.* The sizes of the arrays are returned as *returnColumnSizes array.* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().*///一刷代码,有很多不明白的
int** generateMatrix(int n, int* returnSize, int** returnColumnSizes){//初始化返回的结果数组的大小*returnSize = n;//ColumnSizes的意思是指列的大小*returnColumnSizes = (int*)malloc(sizeof(int) * n);//初始化返回结果数组ans——但是这一坨代码是真不明白啊int** ans = (int**)malloc(sizeof(int) * n);for(int i = 0; i < n; i++){ans[i] = (int*)malloc(sizeof(int) * n);(*returnColumnSizes)[i] = n;}//设置每循环一个圈的起始位置int startX = 0;int startY = 0;//设置二维数组的中间的位置，当n=3那么中间的数就是(1,1)int mid = n / 2;//每个圈循环几次，如果n为奇数3，那么loop=1,只是循环一圈int loop = n / 2;//用来给矩阵中每一个空格赋值int count = 1;//每一圈循环都需要控制每一条边遍历的长度,就是与其他边对接时的右开int offset = 1;//定义行列索引int i ,j;/*这一段是外圈的顺时针遍历*/while(loop){i = startX;j = startY; //顶上的边遍历//n-offset为边界，表示不处理最后一个点for(; j < startY + n - offset; j++){ans[startX][j] = count++;}//右边的边遍历for(; i < startX + n - offset; i++){ans[i][j] = count++;}//底下的边遍历(i=2,j=2开始，因此需要让i不变，j自减)for(; j > startY; j--){ans[i][j] = count++;}//左边的边遍历（从i=2,j=0开始，此时只需要让i自减）for(; i > startX; i--){ans[i][j] = count++;}//第二圈开始时，起始位置各自＋1startX++;startY++;//此时进入内圈，所以偏移值+2offset+=2;loop--;}/*这里是单独给矩阵中间赋值*/if(n % 2 == 1)ans[mid][mid] = count;return ans;
}

这就很胃疼了，我打算下去把晒得被子换一面再回来看，或者干脆下一题。

2023/4/18拖延症犯了前两天，因为是个人学习，所以遇到与些问题一直解决不了的话就会颓废一下，要好好克服一下这点。今天发现是一个地方错了，就是对于两层指针的这里。

第十五行代码那里，自己之前写成了sizeof(int) * n)，因此一直报错，以后要多加注意这种类型题。

以下是正确代码：

/*** Return an array of arrays of size *returnSize.* The sizes of the arrays are returned as *returnColumnSizes array.* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().*///一刷代码,有很多不明白的
int** generateMatrix(int n, int* returnSize, int** returnColumnSizes){//初始化返回的结果数组的大小*returnSize = n;//ColumnSizes的意思是指列的大小*returnColumnSizes = (int*)malloc(sizeof(int) * n);//初始化返回结果数组ans——但是这一坨代码是真不明白啊int** ans = (int**)malloc(sizeof(int*) * n);//注意这里的是int*而不是intfor(int i = 0; i < n; i++){ans[i] = (int*)malloc(sizeof(int) * n);(*returnColumnSizes)[i] = n;}//设置每循环一个圈的起始位置int startX = 0;int startY = 0;//设置二维数组的中间的位置，当n=3那么中间的数就是(1,1)int mid = n / 2;//每个圈循环几次，如果n为奇数3，那么loop=1,只是循环一圈int loop = n / 2;//用来给矩阵中每一个空格赋值int count = 1;//每一圈循环都需要控制每一条边遍历的长度,就是与其他边对接时的右开int offset = 1;//定义行列索引int i ,j;/*这一段是外圈的顺时针遍历*/while(loop){i = startX;j = startY; //顶上的边遍历//n-offset为边界，表示不处理最后一个点for(; j < startY + n - offset; j++){ans[startX][j] = count++;}//右边的边遍历for(; i < startX + n - offset; i++){ans[i][j] = count++;}//底下的边遍历(i=2,j=2开始，因此需要让i不变，j自减)for(; j > startY; j--){ans[i][j] = count++;}//左边的边遍历（从i=2,j=0开始，此时只需要让i自减）for(; i > startX; i--){ans[i][j] = count++;}//第二圈开始时，起始位置各自＋1startX++;startY++;//此时进入内圈，所以偏移值+2offset+=2;loop--;}/*这里是单独给矩阵中间赋值*/if(n % 2 == 1)ans[mid][mid] = count;return ans;
}

疑难分析

自己还是对**这种指针不熟悉，需要多做几道题好好体会一下这类表示。

而且这道题目一开始就没有思路，所以必然后面还要二刷好好体会。

算法复杂度分析

时间复杂度：O(n^2)，模拟遍历二维矩阵的时间

空间复杂度：O(1)

哼哧哼哧写完了，感觉今天的还是挺难的。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！