镇江网站建设优化排名,dede网站运行天数,深圳海外医疗网站建设,甘肃城乡建设厅网站代码随想录二刷 #xff5c; 数组 #xff5c; 有序数组的平方 题目描述题目分析 代码实现暴力排序双指针法 题目描述
977.有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums#xff0c;返回 每个数字的平方 组成的新数组#xff0c;要求也按 非递减顺序 … 代码随想录二刷 数组 有序数组的平方 题目描述题目分析 代码实现暴力排序双指针法 题目描述
977.有序数组的平方
给你一个按 非递减顺序 排序的整数数组 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] 104 nums 已按 非递减顺序 排序
进阶
请你设计时间复杂度为 O(n) 的算法解决本问题
题目分析 代码实现
暴力排序
每个数平方之后再排序
class Solution{
public:vectorint sortedSquares(vectorint A) {for (int i 0; i A.size(); i) {A[i] * A[i];}sort(A.begin(), A.end());return A;}
};时间复杂度O(n nlogn) 双指针法
题目中说数组是非递减排序需要注意的是负数平方之后可能成为最大值因此数组平方后的最大值一定出现在最左侧或最右侧。
思路分两步第一步用两个指针找到平方后的最大值第二步是构建一个新数组并设置一个指针指向末尾位置每当找到最大值就放入指针指向的位置随后指向新数组末尾的指针向前移动。直至 i j。
详细如下
设置一个指针 i 指向初始位置指针 j 指向末尾位置。
定义一个与数组 A 一样大的新数组 result让指针 k 指向 result 数组的末尾位置。
如果A[i] * A[i] A[j] * A[j]那么result[k--] A[j] * A[j]
如果A[i] * A[i] A[j] * A[j]那么result[k--] A[i] * A[i]
class Solution {
public:vectorint sortedSquares(vectorint A) {int k A.size() - 1;vectorint result(A.size(), 0); // 构建一个新数组长度与A相同用0填充// i 指向初始位置j 指向末尾位置直到 i j时结束for (int i 0, j A.size() - 1; i j) { if (A[i] * A[i] A[j] * A[j]) {result[k--] A[i] * A[i];i; // A[i]的平方已经是最大值需要移动 i 指针} else {result[k--] A[j] * A[j];j--; // A[j]的平方已经是最大值需要移动 j 指针}}return result;}
};
