关注Java领域相关技术 记录有趣的事情

LeetCode-977. 有序数组的平方

US-B.Ralph
US-B.Ralph
2020-10-16

问题地址

LeetCode每日一题/2020-10-16

LeetCode977. 有序数组的平方

问题描述

规则

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

示例

  • 示例1
输入：[-4,-1,0,3,10]
输出：[0,1,9,16,100]
  • 示例2
输入：[-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示

  • 1 <= A.length <= 10000
  • 10000 <= A[i] <= 10000
  • A 已按非递减顺序排序。

解析

解题思路

  • 最直观的方法是：遍历原数组对原数组中元素求平方，然后排序；

数据操作分析

  • 见思路分析

复杂度分析

  1. 时间复杂度
  2. 空间复杂度

编码实现

public class LeetCode0977_SquaresOfASortedArray_1 {
    public int[] sortedSquares(int[] A) {
        if (A.length == 0) return A;
        for (int i = 0; i < A.length; i++) {
            int currVal = A[i] * A[i];
            A[i] = currVal;
        }
        Arrays.sort(A);
        return A;
    }
}

优化

  • 先遍历再排序势必导致时间复杂度增加。我们可以在遍历中对结果集进行排序：
  • 原数组有序，但是因为原数组中存在负数，故平方后大数位于原数组两端，不可能在中间，故我们可以考虑使用双指针；
    • 定义一个结果数组ans[]， 让k指向ans[]的末尾；
    • 使用两个指针i,j分别指向A[]的头、尾；
    • 遍历A[]时，比较 A[i] 和 A[j]的平方值；
      • 如果 较大值 赋值给 ans[k--] ，并且 移动i 或 j 指针;

编码实现

public class LeetCode0977_SquaresOfASortedArray {
    public int[] sortedSquares(int[] A) {
        if (A.length == 0) return A;
        int[] ans = new int[A.length];
        int k = A.length - 1;
        for (int i = 0, j = A.length - 1; i <= j; ) {
            if (A[i] * A[i] < A[j] * A[j]) {
                ans[k--] = A[j] * A[j];
                j--;
            } else {
                ans[k--] = A[i] * A[i];
                i++;
            }

        }
        return ans;
    }
}

官方解法

方法一：直接排序

思路与算法：

最简单的方法就是将数组 AA 中的数平方后直接排序。

复杂度分析：

记树上的点的个数为 N。
1. 时间复杂度:O(n \log n)，其中 n 是数组 A 的长度。
2. 空间复杂度：O(logn)。除了存储答案的数组以外，我们需要 O(\log n) 的栈空间进行排序。

编码实现

class Solution {
    public int[] sortedSquares(int[] A) {
        int[] ans = new int[A.length];
        for (int i = 0; i < A.length; ++i) {
            ans[i] = A[i] * A[i];
        }
        Arrays.sort(ans);
        return ans;
    }
}

方法二：双指针

思路：

  • 方法一没有利用「数组 A 已经按照升序排序」这个条件。显然，如果数组 A 中的所有数都是非负数，那么将每个数平方后，数组仍然保持升序；如果数组 A 中的所有数都是负数，那么将每个数平方后，数组会保持降序。
  • 这样一来，如果我们能够找到数组 AA 中负数与非负数的分界线，那么就可以用类似「归并排序」的方法了。具体地，我们设 \textit{neg} 为数组 A 中负数与非负数的分界线，也就是说，A[0] 到 A[\textit{neg}] 均为负数，而 A[\textit{neg}+1] 到 A[n-1] 均为非负数。当我们将数组 A 中的数平方后，那么 A[0] 到 A[\textit{neg}] 单调递减，A[\textit{neg}+1] 到 A[n-1] 单调递增。
  • 由于我们得到了两个已经有序的子数组，因此就可以使用归并的方法进行排序了。具体地，使用两个指针分别指向位置 \textit{neg} 和 \textit{neg}+1，每次比较两个指针对应的数，选择较小的那个放入答案并移动指针。当某一指针移至边界时，将另一指针还未遍历到的数依次放入答案。

复杂度分析：

  1. 时间复杂度:O(n)。其中 n 是数组 A 的长度。

  2. 空间复杂度：O(1)。

编码实现

class Solution {
    public int[] sortedSquares(int[] A) {
        int n = A.length;
        int negative = -1;
        for (int i = 0; i < n; ++i) {
            if (A[i] < 0) {
                negative = i;
            } else {
                break;
            }
        }

        int[] ans = new int[n];
        int index = 0, i = negative, j = negative + 1;
        while (i >= 0 || j < n) {
            if (i < 0) {
                ans[index] = A[j] * A[j];
                ++j;
            } else if (j == n) {
                ans[index] = A[i] * A[i];
                --i;
            } else if (A[i] * A[i] < A[j] * A[j]) {
                ans[index] = A[i] * A[i];
                --i;
            } else {
                ans[index] = A[j] * A[j];
                ++j;
            }
            ++index;
        }

        return ans;
    }
}

方法三：双指针

思路：

  • 同样地，我们可以使用两个指针分别指向位置 00 和 n-1n−1，每次比较两个指针对应的数，选择较大的那个逆序放入答案并移动指针。这种方法无需处理某一指针移动至边界的情况，读者可以仔细思考其精髓所在。

复杂度分析：

  1. 时间复杂度:O(n)。其中 n 是数组 A 的长度。

  2. 空间复杂度：O(1)。

编码实现

class Solution {
    public int[] sortedSquares(int[] A) {
        int n = A.length;
        int[] ans = new int[n];
        for (int i = 0, j = n - 1, pos = n - 1; i <= j;) {
            if (A[i] * A[i] > A[j] * A[j]) {
                ans[pos] = A[i] * A[i];
                ++i;
            } else {
                ans[pos] = A[j] * A[j];
                --j;
            }
            --pos;
        }
        return ans;
    }
}

精彩评论

跳转地址1：各种排序+双指针

思路：

  • 借着这题好好复习一下 各种排序
直接插入排序
int* sortedSquares(int* a, int n, int* returnSize){
    *returnSize=n;
    if(n==0) return a;
    a[0]=a[0]*a[0];
    int j;
    for(int i=1;i<n;i++){
        int temp=a[i]*a[i];
        for(j=i-1;j>=0;j--){
            if(temp<a[j]) a[j+1]=a[j];
            else break;
        }
        a[j+1]=temp;
    }
    return a;
}
折半插入排序
int* sortedSquares(int* a, int n, int* returnSize){
    *returnSize=n;
    if(n==0) return a;
    a[0]=a[0]*a[0];
    int j;
    for(int i=1;i<n;i++){
        int temp=a[i]*a[i];
        int low=0,high=i-1;
        while(low<=high){
            int mid=(low+high)/2;
            if(temp>a[mid]) low=mid+1;
            else high=mi-1;
        }
        for(j=i-1;j>high;j--){
            a[j+1]=a[j];
        }
        a[j+1]=temp;
    }
    return a;
}
选择排序
int* sortedSquares(int* a, int n, int* returnSize){
    *returnSize=n;
    if(n==0) return a;
    int k=0;
    for(int i=0;i<n;i++){
        a[k++]=a[i]*a[i];
    } 
    for(int i=0;i<n-1;i++){
        for(int j=i+1;j<n;j++){
            if(a[j]<a[i]){
                int temp=a[i];
                a[i]=a[j];
                a[j]=temp;
            }
        }
    }
    return a;
}
冒泡排序
int* sortedSquares(int* a, int n, int* returnSize){
    *returnSize=n;
    if(n==0) return a;
    int k=0;
    for(int i=0;i<n;i++){
        a[k++]=a[i]*a[i];
    } 
    for(int i=0;i<n;i++){
        for(int j=0;j<n-i-1;j++){
            if(a[j+1]<a[j]){
                int temp=a[j+1];
                a[j+1]=a[j];
                a[j]=temp;
            }
        }
    }
    return a;
}
带判断条件的冒泡排序
int* sortedSquares(int* a, int n, int* returnSize){
    *returnSize=n;
    if(n==0) return a;
    int k=0;
    for(int i=0;i<n;i++){
        a[k++]=a[i]*a[i];
    } 
    int flag=1;
    while(n>1&&flag==1){
        flag=0;
        for(int j=0;j<n-1;j++){
            if(a[j+1]<a[j]){
                flag=1;
                int temp=a[j+1];
                a[j+1]=a[j];
                a[j]=temp;
            }
        }
    }
    return a;
}
快排
int Pattion(int *a,int low,int high){
    int temp=a[low],pivoty=a[low];
    while(low<high){
        while(a[high]>=pivoty&&low<high) high--;
        a[low]=a[high];
        while(a[low]<=pivoty&&low<high) low++;
        a[high]=a[low];
    }
    a[low]=temp;
    return low;
}
void QuickSort(int *a,int low,int high){
    int p;
    if(low<high){
        p=Pattion(a,low,high);
        QuickSort(a,low,p-1);
        QuickSort(a,p+1,high);
    }
}

int* sortedSquares(int* a, int n, int* returnSize){
    *returnSize=n;
    if(n==0) return a;
    int k=0;
    for(int i=0;i<n;i++){
        a[k++]=a[i]*a[i];
    }
    QuickSort(a,0,n-1); 
    return a;
}
归并排序
void MergeSort(int *a,int low,int mid,int high){

    int *b=(int *)malloc(sizeof(int)*(high+1));
    for(int i=low;i<=high;i++){
        b[i]=a[i];
    }
    int i=low,j=mid+1,temp=low;
    while(i<=mid&&j<=high){
        if(b[i]<b[j]){
            a[temp++]=b[i++];
        }
        else a[temp++]=b[j++];
    }
    while(i<=mid) a[temp++]=b[i++];
    while(j<=high) a[temp++]=b[j++];

}
void Merge(int *a,int low,int high){
    int mid;
    if(low==high)return ;
    else{
        mid=(low+high)/2;
        Merge(a,low,mid);
        Merge(a,mid+1,high);
        MergeSort(a,low,mid,high);

    }
} 
int* sortedSquares(int* a, int n, int* returnSize){
    *returnSize=n;
    if(n==0) return a;
    int k=0;
    for(int i=0;i<n;i++){
        a[k++]=a[i]*a[i];
    }
    Merge(a,0,n-1); 
    return a;
}
双指针
int* sortedSquares(int* a, int n, int* returnSize){
    *returnSize=n;
    if(n==0) return a;
    int p=0,q=-1;
    for(int i=0;i<n;i++){
        if(a[i]>=0) {
            p=i;
            q=i-1;
            break;
        }
    } 
    int k=0;
    int *res=(int *)malloc(sizeof(int)*n);
    while(p<n&&q>=0){
        if(a[p]*a[p]<a[q]*a[q]){
            res[k++]=a[p]*a[p];
            p++;
        }
        else{
            res[k++]=a[q]*a[q];
            q--;
        } 
    } 
    while(p<n) {
        res[k++]=a[p]*a[p];
        p++;
    }
    while(q>=0){
        res[k++]=a[q]*a[q];
        q--;
    }
    return res;
}
US-B.Ralph
LeetCode数据结构与算法算法

One Comment

  • erotik

    Say, you got a nice blog post. Much thanks again. Really Great. Robby Humfrey Motch

    Reply

Leave a Comment

邮箱地址不会被公开。 必填项已用*标注

19 − 2 =