977 Array 有序数组的平方

2020-10-17

思路

定义一个数组变量 reArray ，用来存储原数组数组元素的平方，

然后对新的数组进行冒泡排序。

暴力破解法 - 直接排序

public int[] sortedSquares(int[] A) {
    // int len = A.length;
    int[] reArray = new int [A.length];
    for(int i=0;i< A.length;i++){
        reArray[i] = A[i]*A[i];
    }
    // 排序
    // for(int i=0;i<len-1;i++){
    //     for(int j = 0;j<len-1-i;j++){
    //         if(reArray[j] > reArray[j+1]){
    //             int temp = reArray[j];
    //             reArray[j]=reArray[j+1];
    //             reArray[j+1]=temp;
    //         }
    //     }
    // }
    Arrays.sort(reArray);
    return reArray;
}

复杂度分析

时间复杂度：O(n log n)O(nlogn)，其中 n是数组 A 的长度。

空间复杂度：O(log n)O(logn),除了存储答案的数组以外，我们需要 O(log n)O(logn)的栈空间进行排序。

方法二双指针法

因为原来的数组是递增排序的，所以会出现如下情况：

所有元素 > 0 或者 < 0 ,那么平方之后的数组依然是有序的
存在一个边界数字，把左右两边分成正数和负数，平方之后一边单调递增，一边单调递减

算法：

找出边界数字 edge，元素全为 + edge = -1，元素全为-，edge= len-1
双指针算法：
- 变量 i = edge 为左边元素的边界（绝对值最小），变量 j = edge +1位右边元素的边界（绝对值最小）
- i< 0 ，元素全为 +，此时 edge = -1，j = 0
- j == len ，元素全为 -，此时 i = len-1
- 除此之外，比较左右元素的边界($A[i]^2 和 A[j]^2$)
  - 设置一个变量 index = 0 ，如果左边小，左指针左移，继续比较
  - 如果右边小，右指针右移

// 找出边界
int edge = -1;
for(int i=0;i<len;i++){
    if(A[i] < 0){
        edge = i;
    }else {
        break;
    }
}

// 双指针
int i = edge,j=edge+1;
int index = 0;
while(i>=0 || j<len){
    // 都为 +,此时 j 初始为 0，A[j]是最小的元素
    if(i<0){
        reArray[index] = A[j]*A[j];
        j++;
    }else if(j==len){
        // 全为-，此时 i = len-1，A[i]是最小的元素
        reArray[index] = A[i]*A[i];
        i--;
    }else if(A[j]*A[j] > A[i]*A[i] ){
        reArray[index] = A[i]*A[i];
        i--;
    }else{
        reArray[index] = A[j]*A[j];
        j++;
    }
    index++;
}

return reArray;

时间复杂度：O(n)O(n)，其中 nn 是数组 AA 的长度。
空间复杂度：O(1)O(1)。

方法三：双指针

不找边界，假设左边是一个负数数组，右边是一个正数数组。i 指向负数数组的第一位，j 指向正数数组的最后一位。因为左右边界数字都是绝对值最大的，所以每次只能比较出数组中最大值，数组选择逆序存储。比较边界的数字，大的存入数组并移动指针，通过 i <= j 来结束指针的移动。

// 双指针 不找边界法 逆序存储数组	
for(int i = 0,j=len-1,pos = len-1;i <= j;){// ; 不能少
    if(A[j]*A[j] > A[i]*A[i]){
        reArray[pos] = A[j]*A[j];
        j--;
    }else{
        reArray[pos] = A[i]*A[i];
        i++; 
    }
    pos--;
}

暴力破解法 - 直接排序

方法二 双指针法

方法三：双指针

方法二双指针法