给你一个按 非递减顺序 排序的整数数组 nums
,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。
:
class Solution {public int[] sortedSquares(int[] nums) {// 找到绝对值最小的数下标int minIdx = -1;int min = Integer.MAX_VALUE;int len = nums.length;for(int i = 0; i < len; i++){if(min > Math.abs(nums[i])) {min = Math.abs(nums[i]);minIdx = i;}nums[i] = nums[i] * nums[i];}// 以这个最小下标为界,int max = Integer.MAX_VALUE;int l = minIdx - 1;int r = minIdx + 1;int[] ans = new int[len];ans[0] = min * min;int i = 1;// 必须满足其一,才能进入循环。当都不满足的时候,就是ans赋值完毕的时候。while(l >= 0 || r < len) {if(l == -1) {ans[i++] = nums[r++];continue;} else if(r == len) {ans[i++] = nums[l--];continue;}// if(nums[l] > nums[r]) ans[i++] = nums[r++];// else ans[i++] = nums[l--]; ans[i++] = nums[l] > nums[r] ? nums[r++] : nums[l--];}return ans;}
}
:基本相同写法(将双指针从中将最小值的下表,向两边移动)
public int[] sortedSquares(int[] nums){int n = nums.length;// 先找到绝对值最小的下标int minIdx = -1;int min = Integer.MAX_VALUE;for(int i = 0; i < n; i++){if(min > Math.abs(nums[i])) {min = Math.abs(nums[i]);minIdx = i;}// 顺便将数组的数都平方nums[i] = nums[i] * nums[i];}// 以minIdx为分界,分为左右两部分int[] ans = new int[n];ans[0] = nums[minIdx];int l = minIdx - 1, r = minIdx + 1;int i = 1;while(l >= 0 && r < n) {ans[i++] = nums[l] < nums[r] ? nums[l--] : nums[r++];}// 左部分或者右部分结束了一个if(l == -1) {while(r < n) ans[i++] = nums[r++];} else while(l >= 0) ans[i++] = nums[l--];return ans;
}
:将双指针l、r分别从头和尾向中间移动(简化了很多,不用再处理边界条件)
class Solution{public int[] sortedSquares(int[] nums){int n = nums.length;// 先找到绝对值最小的下标int minIdx = -1;int min = Integer.MAX_VALUE;for(int i = 0; i < n; i++){if(min > Math.abs(nums[i])) {min = Math.abs(nums[i]);minIdx = i;}// 顺便将数组的数都平方nums[i] = nums[i] * nums[i];}// 以minIdx为分界,分为左右两部分int[] ans = new int[n];ans[0] = nums[minIdx];int l = 0, r = n - 1;int i = n - 1;while(l < minIdx || r > minIdx) {ans[i--] = nums[l] > nums[r] ? nums[l++] : nums[r--];}return ans;}
}