🌟个人博客：www.hellocode.top🌟
?所有文章均在上方博客首发，其他平台同步更新
🔥本文专栏：《每日一题》
?如有问题，欢迎指正，一起学习~~
文章部分参考《代码随想录》，如有侵权，请联系删除~~
-
时间：2022-05-10
-
题目序号：977
-
难度：简单
问题描述
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
来源：力扣（LeetCode）
示例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已按 非递减顺序 排序
解题思路
题解部分参考自代码随想录。如有侵权，请联系进行删除~~
- 在解题时，我们都可以先思考暴力解法进行解题，然后再通过逐步优化，来提高代码的性能
- 对于本题，可以通过暴力和双指针两种方法进行解决
暴力解法
- 根据本题的题目描述，暴力解法其实很容易就能想到
- 直接通过for循环遍历数组，让nums[i] *= nums[i]即可
- 在遍历结束后，数组内的值就已经是平方后的值了，只不过不是按顺序排列，使用Arrays里的sort方法进行排序即可（快排）
双指针解法
- 原数组中的元素其实是有序的，主要是进行平方后数组中数据的排序
- 不难想到，平方后，最大的值一定是最左边或者最右边的值，不可能是中间的元素
- 因此，可以定义两个指针，一个指向数组首元素，一个指向数组尾元素
- 根据上图中的if条件进行判断循环，最终即可获得有序的平方值
代码实现
通过上述分析，分别可以通过暴力解法和双指针解法两种方式来实现移除元素
暴力解法
class Solution {
public int[] sortedSquares(int[] nums) {
for(int i = 0; i < nums.length; i++){
nums[i] *= nums[i];
}
Arrays.sort(nums);
return nums;
}
}
- 时间复杂度：O(nlogn)
双指针解法
class Solution {
public int[] sortedSquares(int[] nums) {
int size = nums.length;
int[] result = new int[size];
int left = 0;
int right = size - 1;
int index = size - 1;
while(left <= right){
if(nums[left] * nums[left] < nums[right] * nums[right]){
result[index--] = nums[right] * nums[right];
right--;
}else{
result[index--] = nums[left] * nums[left];
left++;
}
}
return result;
}
}
- 时间复杂度：O(n)
总结
- 一般遇到一个问题时，可以先考虑暴力解法，然后再考虑其他更加高效的算法或者对暴力解法进行不断优化，来提高算法的效率
- 数组操作中的很多地方都会用到双指针解法，所以对于双指针一定要掌握并能够灵活的运用
- 在有索引的地方，对于临界值的判断一定要准确，什么时候
<=，什么时候<，要能够分清
