大连网站开发培训,帮客户做插边球网站,全球咨询公司排名,葫芦岛建设厅网站一、977.有序数组的平方的链接与题目描述
977. 有序数组的平方的链接如下所示#xff1a;https://leetcode.cn/problems/squares-of-a-sorted-array/description/https://leetcode.cn/problems/squares-of-a-sorted-array/description/ 给你一个按 非递减顺序 排序的整数数组…一、977.有序数组的平方的链接与题目描述
977. 有序数组的平方的链接如下所示https://leetcode.cn/problems/squares-of-a-sorted-array/description/https://leetcode.cn/problems/squares-of-a-sorted-array/description/ 给你一个按 非递减顺序 排序的整数数组 nums返回 每个数字的平方 组成的新数组要求也按 非递减顺序 排序。 示例 1 输入nums [-4,-1,0,3,10]输出[0,1,9,16,100]解释平方后数组变为 [16,1,0,9,100]排序后数组变为 [0,1,9,16,100] 示例 2 输入nums [-7,-3,2,3,11]输出[4,9,9,49,121]提示
1 nums.length 104-104 nums[i] 104nums 已按 非递减顺序 排序 进阶
请你设计时间复杂度为 O(n) 的算法解决本问题 二、977.有序数组的平方的c代码 第一种方法双指针的时间复杂度o(n)具体代码如下 vectorint result(nums.size(), 0);int nnums.size()-1;int left0, rightn;while(leftright){if(pow(nums[left], 2)pow(nums[right], 2)){result[n--]pow(nums[left], 2);left;}else{result[n--]pow(nums[right], 2);right--;}}return result; 第二种方法快速排序的时间复杂度o(nlogn) 具体代码如下 for(int i0;inums.size()-1;i){nums[i]*nums[i]; //快速排序}sort(nums.begin(), nums.end());return nums; 三、解题思路 本题主要讲解双指针的算法思路下面的本题的4个步骤
定义左指针的索引值为0右指针为nums.size()-1容器result装平方后的数组元素用while判断条件如果左指针的值小于等于右指针的值则循环继续反之则终止判断数组开始的值的平方是否大于末尾的值的平方如果大于输入result[n--]pow(nums[left], 2); left反之则result[n--]pow(nums[right], 2); right--;最后输出result得出答案。 感谢各位读者的阅读与支持您的支持是我前进的动力我希望我的博文能够带给您双指针的一些算法知识和启发。如果您有任何问题或意见请随时联系我或在评论区评论。希望本题的算法知识对大家有帮助谢谢各位读者的支持
