给你一个按 非递减顺序 排序的整数数组 nums
,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。
基础使用先平方,后排序的思想
class Solution {public int[] sortedSquares(int[] nums) {for(int i=0;i<nums.length;i++){nums[i] = nums[i] * nums[i];}for(int j=0;j<nums.length;j++) {for(int i=0;i<nums.length-1-j;i++) {if(nums[i]>nums[i+1]) {//进行交换int temp = nums[i];nums[i] = nums[i+1];nums[i+1] = temp;}}}return nums;}
}
但这种方法执行过慢
因此引入,双指针思想:每次比较两个指针对应的数,选择较大的那个逆序放入答案并移动指针
class Solution {public int[] sortedSquares(int[] nums) {int n = nums.length;int[] arr = new int[n];for (int i = 0, j = n - 1, index = n - 1; i <= j;) {if (nums[i] * nums[i] > nums[j] * nums[j]) {arr[index] = nums[i] * nums[i];++i;} else {arr[index] = nums[j] * nums[j];--j;}--index;}return arr;}
}