美文网首页
977. 有序数组的平方

977. 有序数组的平方

作者: mydre | 来源:发表于2020-11-05 13:28 被阅读0次

给定一个按非递减顺序排序的整数数组 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 已按非递减顺序排序。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/squares-of-a-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

image.png

数组的数值分布有三种情况。其中第一种和第三种情况,都比较容易处理。第一种情况的处理方式是平方之后直接返回,第三种情况是平方之后进行reverse即可(这是因为负数越小,则平方之后的数值越大)。
我们重点处理第二种情况。这个时候我们需要找到数组中值在0附近的元素对应的下标i。然后可以从i出发,分别向左和向右遍历数组,从而我们可以根据这两个有序数组中的元素来构造一个包含这两个数组中所有元素的新的数组。

代码

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
 void pingfang(int *A,int ASize){//把数组中的元素求平方
     for(int i = 0;i< ASize;i++){
         A[i] = A[i] * A[i];
     }
 }
void reverse(int *A,int ASize){//对数组进行reverse操作
    int t = ASize/2;
    int temp;
    for(int i = 0;i<t;i++){
        temp = A[i];
        A[i] = A[ASize -1 -i];
        A[ASize -1 -i] = temp;
    }
}

int* sortedSquares(int* A, int ASize, int* returnSize){
    *returnSize = ASize;
    
    int *res = (int *)malloc( ASize * sizeof(int));
    int r = 0;
    int i = 0,j = 0;
    if(A[0] >= 0){//第一种情况
        pingfang(A,ASize);
        return A;
    }else if(A[0] < 0){
        if(A[ASize-1] <=0){//第三种情况
            pingfang(A,ASize);
            reverse(A,ASize);
            return A;
        }else{//第二种情况
            i = 0;
            while(i+1 < ASize){
                if(A[i] <= 0 && A[i+1] >=0){
                    break;
                }
                i++;
            }
            pingfang(A,ASize);
            int a = i;
            int b = i+1;
            while(a >= 0 && b < ASize){
                if(A[a] < A[b]){
                    res[r++] = A[a--];
                }else{
                    res[r++] = A[b++];
                }
            }
            while(a >= 0){
                res[r++] = A[a--];
            }
            while(b < ASize){
                res[r++] = A[b++];
            }
        }
    }
    return res;
}

相关文章

  • 977. 有序数组的平方

    //977. 有序数组的平方https://leetcode-cn.com/problems/squares-of...

  • 61.有序数组的平方

    day13: 977. 有序数组的平方[https://leetcode-cn.com/problems/squa...

  • 第 2 天 双指针

    977. 有序数组的平方 给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组...

  • ARTS Week 01

    Algorithm 题目 977. 有序数组的平方给定一个按非递减顺序排序的整数数组 A,返回每个数字的平方组成的...

  • 977. 有序数组的平方

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

  • 977. 有序数组的平方

    【题目描述】给定一个按非递减顺序排序的整数数组 A,返回每个数字的平方组成的新数组,要求也按非递减顺序排序。 【示...

  • 977. 有序数组的平方

    给定一个按非递减顺序排序的整数数组 A,返回每个数字的平方组成的新数组,要求也按非递减顺序排序。 示例 1: 输入...

  • 977.有序数组的平方

    题目 给定一个按非递减顺序排序的整数数组 A,返回每个数字的平方组成的新数组,要求也按非递减顺序排序。 示例 1:...

  • LeetCode 977. 有序数组的平方

    题目 给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 ...

  • [LeetCode][Python]977. 有序数组的平方

    给定一个按非递减顺序排序的整数数组 A,返回每个数字的平方组成的新数组,要求也按非递减顺序排序。 示例 1: 输入...

网友评论

      本文标题:977. 有序数组的平方

      本文链接:https://www.haomeiwen.com/subject/nfwovktx.html