Leetcode日记— 977. Squares of a Sorted Array

发布于 2020-10-16  109 次阅读


碎碎念:嗯,买了新电脑了,并夕夕下单,希望不要翻车。

题目如下:

Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order.

Example 1:

Input: [-4,-1,0,3,10]
Output: [0,1,9,16,100]

Example 2:

Input: [-7,-3,2,3,11]
Output: [4,9,9,49,121]

思路:

最无脑的方法就是所有的数都平方后重新排序,作为答案return。

其次,我们观察到这个数组是个非递减序列,也就是说数组两端的数字一定是绝对值最大的数字。那么我们用一个双指针,分别放在数组的两端,每次比较中较大的数进行平方并存在res数组的尾部,指针向中间移动。这样就达到了一次遍历就可以得到答案。

代码如下:

class Solution {
    public int[] sortedSquares(int[] A) {
        if(A==null)
            return A;
        int count = A.length - 1;
        int[] res = new int[count+1] ;
        int leftPointer = 0;
        int rightPointer = count;
        for(;count>=0;count--){
            if(Math.abs(A[leftPointer])>=A[rightPointer]){
                res[count] = (int) Math.pow(A[leftPointer],2);
                leftPointer++;
            }
            else{
                res[count] = (int) Math.pow(A[rightPointer],2);
                rightPointer--;
            }
        }
        return res;
    }
}

同样的,另一种思路就是先找到正负数的分界点。(有点归并排序那味儿了)每次绝对值较小的数平方并放入结果数组中,然后两个指针向两头移动。

代码如下:

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;
    }
}

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/squares-of-a-sorted-array/solution/you-xu-shu-zu-de-ping-fang-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

你好哇!欢迎来到雷公马碎碎念的地方:)