977.有序数组的平方

题目

给定一个按非递减顺序排序的整数数组 A，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。

示例 1：

输入：[-4,-1,0,3,10]
输出：[0,1,9,16,100]

示例 2：

输入：[-7,-3,2,3,11]
输出：[4,9,9,49,121]

题解

1. 先进行数组每个元素的平方操作，排除正负数影响。
2. 采用冒泡方法进行排序

注意事项

• 冒泡排序和选择排序不要混淆，记好各自的代码模板

图示

image.png

复杂度分析

• 时间复杂度：
• 空间复杂度：

代码

class Solution {

    /**
     * 每次冒泡交换相邻两个元素，直到最后选出最大的元素
     * 外层次数为 n-1; n从1开始
     * 里层次数 为 n - i;
     */
    public int[] sortedSquares(int[] A) {
        int[] result = new int[A.length]; 
        for(int j = 0; j < result.length; j++){
            result[j] = A[j] * A[j];
        }
        //外层比较的次数
        for(int k = 1; k < result.length; k++){
            //设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成
            boolean flag = true;

            for(int i = 0; i < result.length - k; i++){
                if(result[i] > result[i+1]){
                    int temp = result[i];
                    result[i] = result[i+1];
                    result[i+1] = temp;
                    flag = false;
                }
            }
            if(flag)
                break;           
        }
        return result;
    }
}