977. 有序数组的平方

分析

其实一看到这个题目，我想到的就是重新根据绝对值排序，同时官方题解根据非递减顺序排序这个特征，指出了，排序的具体操作，那就是两头的数字肯定比中间的大，我们用两个指针，一个指向头，一个指向尾，把大的拿出来放到结果的末尾中，这样直到两个指针相遇或者结果数组被填满，这样的话，那我干脆就直接比较元素的平方算了，就不用比较元素的绝对值了。

解题

注意，非递减排序，等于增量排序，且有重复元素，
而且题目中也提示了 -104 <= nums[i] <= 104 ，因此元素的平方也可以用 int 类型来保存
从两头开始比较，把大的放到结果数组的末尾。
在循环中比较 start 和 end 指向的元素的时候，循环条件为 start<=end ，也就说必须处理 nums[start] 和 nums[end] 相等的情况，而且前面我们也提到过数组中可能出现重复元素，因此循环中必须处理 nums[start] 和 nums[end] 相等的情况。
因为我们只遍历了一遍数组，假设数组的元素个数为 n，算法复杂度就是 $O (n)$

public int[] sortedSquares(int[] nums) {
    int[] target = new int[nums.length];
    int tIndex =nums.length-1;
    int start=0,end=nums.length-1;
    for(;start<=end;){
        // start 和 end 可能指向同一个元素，因此循环中必须处理元素相同的情况。
        int targetEle = -1;
        if(nums[start]*nums[start] > nums[end]*nums[end]){
	        // 将大的那个元素放到结果数组的后面
            targetEle = nums[start]*nums[start];
            start++;
        }else{
			// 元素相等的时候也移动
            targetEle = nums[end]*nums[end];
            end--;
        }
        target[tIndex] = targetEle;
        tIndex--;
    }
    return target;
}

其实也可以使用 tIndex>=0 为条件，都是一样的，很简单。下面这种更好理解一点。

class Solution {
    public int[] sortedSquares(int[] nums) {
        // 从两边到中间
        int[] result = new int[nums.length];
        int left=0,right=nums.length-1;
        int nexResultIndex = result.length-1;
        while(nexResultIndex>=0){
            int leftSqrt = nums[left]*nums[left];
            int rightSqrt = nums[right]*nums[right];
            if(leftSqrt<=rightSqrt){
		        // 将大的那个元素放到结果数组的后面
                result[nexResultIndex] =rightSqrt;
                nexResultIndex--;
                right--;
            }else{
                result[nexResultIndex] =leftSqrt;
                nexResultIndex--;
                left++;
            }
        }
        return result;
    }
}

977. 有序数组的平方

分析

解题

相关题